Turing's Palindrome - 照猫画虎 | Scarecrow = 2022

# 状态

s1：start
s2：right
s3：left
s4：halt
s5：break (失败)
我不是很确定状态是不是可以自己定，按我的理解 break 则说明字符串的首尾 (包括缩短后的串) 匹配不超过，而 halt 则说明全部匹配完毕，回文串判断完毕

# 大致思路

非回文与回文分别以 abcab 和 abcba 为例，记录过程和结果 (每一步的纸带布局、状态)。

# 失败

ID	当前状态	当前符号	写入	移动	新状态
1	s1	a	&	r	s2
2	s2	b	b	r	s2
3	s2	c	c	r	s2
4	s2	a	&	r	s2
5	s2	b	b	r	s2
6	s2	b	null	l	s3->s5

# 成功

ID	当前状态	当前符号	写入	移动	新状态
1	s1	a	&	r	s2
2	s2	b	b	r	s2
3	s2	c	c	r	s2
4	s2	b	b	r	s2
5	s2	a	&	r	s2
6	s2	&	&	l	s3
7	s3	b	^	l	s3
8	s3	^	c	l	s3
9	s3	c	^	l	s3
10	s3	^	^	r	s2
11	s2	^	$	r	s2
12	s2	$	$	l	s4

# Turing Machine

Turing Machine for palindromes

# Class with these elements

状态（名为 state 的字符串）
写入头（名为 write_head 的整数）
磁带（名为 tape_list 的列表）

	class Turing_Machine:

	def __init__(self,state,write_head,tape_list):
	self.state = state
	self.write_head = write_head
	self.tape_list = tape_list

	def getState(self):
	return self.state

	def getHead(self):
	return self.write_head

	def getList(self):
	return self.tape_list

	# Table of rules
	def updateMachine(self, character_list):

	# Initial State
	if (self.state == 'q1'):
	if (self.tape_list[self.write_head] != 0):
	### STATE ### (p)
	char_read = self.tape_list[self.write_head]
	char_index = character_list.index(char_read)
	self.state = ''.join(['p',str(char_index)])
	### WRITE ### (zero)
	self.tape_list[self.write_head] = 0
	### MOVE ### (right)
	self.write_head += 1
	else:
	### STATE ### (qy)
	self.state = 'qy'
	### WRITE ### (zero, unchanged)
	self.tape_list[self.write_head] = 0
	### MOVE ### (right) (doesnt matter)
	self.write_head += 1

	elif (self.state.startswith('p')):
	if (self.tape_list[self.write_head]!=0):
	### STATE ### (unchanged)
	self.state = self.state
	### WRITE ### (unchanged)
	self.tape_list[self.write_head] = self.tape_list[self.write_head]
	### MOVE ### (right)
	self.write_head += 1
	else:
	### STATE ### (r)
	self.state = ''.join(['r',self.state[1:]])
	### WRITE ### (zero, unchanged)
	self.tape_list[self.write_head] = 0
	### MOVE ### (left)
	self.write_head -= 1

	elif (self.state.startswith('r')):
	char_read = character_list[int(self.state[1:])]
	if (self.tape_list[self.write_head] != char_read and self.tape_list[self.write_head] != 0): # zero is needed for strings of odd length
	### STATE ### (qn)
	self.state = 'qn'
	### WRITE ###
	self.tape_list[self.write_head] = self.tape_list[self.write_head]
	### MOVE ### (left) (doesn't matter)
	self.write_head -= 1
	else:
	### STATE ###
	self.state = 'q2'
	### WRITE ### (zero)
	self.tape_list[self.write_head] = 0
	### MOVE ### (left)
	self.write_head -= 1

	elif (self.state == 'q2'):
	if (self.tape_list[self.write_head] != 0):
	### STATE ### (unchanged)
	self.state = 'q2'
	### WRITE ### (unchanged)
	self.tape_list[self.write_head] = self.tape_list[self.write_head]
	### MOVE ### (left)
	self.write_head -= 1
	else:
	### STATE ### (q1)
	self.state = 'q1'
	### WRITE ### (zero)
	self.tape_list[self.write_head] = 0
	### MOVE ### (right)
	self.write_head += 1

# Setting up input/output

需要一种方法将字符串输入到程序中，设置机器的初始状态、起始写入头位置，并将字符串写入磁带。

	import string
	import sys
	from turing import Turing_Machine

	def check_palindrome(initial_string):

	# Define Character Set (allowed characters for the palindrome)
	character_list = list(string.ascii_lowercase)
	character_list.append(' ') # to allow for spaces

	# Initial string
	print('Checking: ' + initial_string)
	print('- - -')
	initial_list = list(initial_string)

	# Quick check that you only used allow characters
	for i in initial_list:
	if i not in character_list:
	print('Error! Initial character >',i,'< not in allowed character list!')
	sys.exit()

	# Append list
	initial_list.append(0)

	# Set up the turing machine
	i_write_head = 0
	i_state = 'q1' # initial state
	i_tape_list = initial_list

	# Initiate the class
	runMachine = Turing_Machine(i_state,i_write_head,i_tape_list)
	print(runMachine.getState(),runMachine.getHead(),runMachine.getList())

	# Run the machine
	ctr=0
	while runMachine.getState() != 'qy' and runMachine.getState() != 'qn' and ctr < 1000:
	runMachine.updateMachine(character_list)
	print(runMachine.getState(),runMachine.getHead(),runMachine.getList())
	ctr += 1
	print('- - -')

	# Printout result
	if (runMachine.getState() == 'qy'):
	print(initial_string,'is a palindrome! Steps:',ctr)
	else:
	print(initial_string,'is NOT a palindrome! Steps:',ctr)

# Running the code

每次迭代时访问状态，以检查程序是否已完成（状态 qn 或 qy ）。创建一个名为 “test.py” 的文件，其中包含以下内容：

	import sys

	from palindrome import check_palindrome

	if __name__ == "__main__":

	if len(sys.argv) != 2:
	print("Usage:")
	print("python test.py word")
	print("where word is the word to be tested as a palindrome")
	sys.exit(0)

	word = sys.argv[1]
	check_palindrome(word)

# 控制台

# 失败

	PS C:\Users\FYGOD\turing_machines_palindromes-master> python test.py abcab
	Checking: abcab
	- - -
	q1 0 ['a', 'b', 'c', 'a', 'b', 0]
	p0 1 [0, 'b', 'c', 'a', 'b', 0]
	p0 2 [0, 'b', 'c', 'a', 'b', 0]
	p0 3 [0, 'b', 'c', 'a', 'b', 0]
	p0 4 [0, 'b', 'c', 'a', 'b', 0]
	p0 5 [0, 'b', 'c', 'a', 'b', 0]
	r0 4 [0, 'b', 'c', 'a', 'b', 0]
	qn 3 [0, 'b', 'c', 'a', 'b', 0]
	- - -
	abcab is NOT a palindrome! Steps: 7

# 成功

	PS C:\Users\FYGOD\turing_machines_palindromes-master> python test.py abcba
	Checking: abcba
	- - -
	q1 0 ['a', 'b', 'c', 'b', 'a', 0]
	p0 1 [0, 'b', 'c', 'b', 'a', 0]
	p0 2 [0, 'b', 'c', 'b', 'a', 0]
	p0 3 [0, 'b', 'c', 'b', 'a', 0]
	p0 4 [0, 'b', 'c', 'b', 'a', 0]
	p0 5 [0, 'b', 'c', 'b', 'a', 0]
	r0 4 [0, 'b', 'c', 'b', 'a', 0]
	q2 3 [0, 'b', 'c', 'b', 0, 0]
	q2 2 [0, 'b', 'c', 'b', 0, 0]
	q2 1 [0, 'b', 'c', 'b', 0, 0]
	q2 0 [0, 'b', 'c', 'b', 0, 0]
	q1 1 [0, 'b', 'c', 'b', 0, 0]
	p1 2 [0, 0, 'c', 'b', 0, 0]
	p1 3 [0, 0, 'c', 'b', 0, 0]
	p1 4 [0, 0, 'c', 'b', 0, 0]
	r1 3 [0, 0, 'c', 'b', 0, 0]
	q2 2 [0, 0, 'c', 0, 0, 0]
	q2 1 [0, 0, 'c', 0, 0, 0]
	q1 2 [0, 0, 'c', 0, 0, 0]
	p2 3 [0, 0, 0, 0, 0, 0]
	r2 2 [0, 0, 0, 0, 0, 0]
	q2 1 [0, 0, 0, 0, 0, 0]
	q1 2 [0, 0, 0, 0, 0, 0]
	qy 3 [0, 0, 0, 0, 0, 0]
	- - -
	abcba is a palindrome! Steps: 23

思考图灵纸带机回文串实验作业 Python