Welcome, guest | Sign In | My Account | Store | Cart

A Turing Machine Simulator that allows an arbitrary machine to be loaded. Words (represented as strings) can be ran against the simulator producing a response: Accept or Crash.

Python, 160 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#!/usr/bin/env python

# (C) 2003 Ryan Phillips

import sys

pr = sys.stdout.write

class MachineTapeException(Exception):
	""" Turing Exception Exception """
	def __init__(self, value):
		Exception.__init__(self)
		self.value = value
	def __str__(self):
		return self.value

class TuringErrorException(Exception):
	""" Turing Exception Exception """
	def __str__(self):
		return "Crash"

class TuringAcceptException(Exception):
	""" Turing Accept Exception """
	def __str__(self):
		return "Accept"

class MachineTape:
	def __init__(self, initialString=[], initialPos=0, blank="_"):
		""" The Tape uses a simple list.  It could easily be changed into a string if
		    need be """
		self.tape = []
		self.pos = initialPos
		self.blank = blank
		self.initialString = initialString
		if len(initialString) > 0:
		    for ch in initialString:
			    self.tape.append(ch)
		else:
		    self.tape.append(blank)

	def reinit(self):
		self.__init__(self.initialString)

	def move(self, check_char, changeto_char, direction):
		""" Only R, L directions are supported """
		# check to see if the character under the head is what we need
		if check_char != self.tape[self.pos]:
			raise MachineTapeException ("Tape head doesn't match head character")
		
		# at this point the head is over the same character we are looking for
		#  change the head character to the new character
		self.tape[self.pos] = changeto_char
		
		if direction == "L":
			self.move_left()
		elif direction == "R":
			self.move_right()
		else: raise MachineTapeException ("Direction is invalid")
	
	def read(self):
		""" return the character over the head """
		return self.tape[self.pos]
	
	def move_left(self):
		if self.pos <= 0: 
			self.tape.insert(-1, self.blank)
			self.pos = 0
		else:
			self.pos += -1

	def move_right(self):
		self.pos += 1
		if self.pos >= len(self.tape): self.tape.append(self.blank)
	
	def show(self):
		""" print the tape """
		for ch in self.tape:
			pr(ch)
		pr("\n"); pr(" "*self.pos + "^"); pr("\n")

"""
The program structure for the TM is created with a dictionary.
    To step algorithm:
	1. Check to see if the length of the string is zero and if we
	    are in a final state
	2. If the currentstate is in the final states then raise an Accept
	3. If the currentstate is not in the program then raise an Error
	4. Check the head character
	5. If the head character is not in the program and in the current state then
	    raise an Error
	6. Retrieve from the dictionary the dest_state, char_out, and movement
	7. set the current state to the new state
	8. write the tape, and move the head

Program Layout:
    [state][char_in] --> [(dest_state, char_out, movement)]
"""

class TuringMachine:
	def __init__(self, initialString, finalStates=[], blank="_"):
		self.blank = blank
		self.tape = MachineTape(initialString)
		self.fstates = finalStates
		self.program = {}
		self.initState = 0
		self.state = self.initState
		self.lenStr = len(initialString)
	
	def reinit(self):
		self.state = self.initState
		self.tape.reinit()
	
	def addTransition(self, state, char_in, dest_state, char_out, movement):
		if not self.program.has_key(state):
			self.program[state] = {}

		tup = (dest_state, char_out, movement)
		self.program[state][char_in] = tup

	def step(self):
		""" Steps 1 - 3 """
		if self.lenStr == 0 and self.state in self.fstates: raise TuringAcceptException
		if self.state in self.fstates: raise TuringAcceptException 
		if self.state not in self.program.keys(): raise TuringErrorException
		
		""" Steps 4 and 5 """
		head = self.tape.read()
		if head not in self.program[self.state].keys(): raise TuringErrorException
			
		""" Steps 6 and 7 """
		# execute transition
		(dest_state, char_out, movement) = self.program[self.state][head]
		self.state = dest_state
		try:
			""" Step 8 """
			self.tape.move(head, char_out, movement)
		except MachineTapeException, s:
			print s

	def execute(self):
		""" The TM will keep stepping forever until the TM accepts or rejects.
		    This does allow for looping TM's """
		try:
			while 1:
				m.tape.show()
				m.step()
		except (TuringErrorException, TuringAcceptException), s:
			print s

if __name__ == "__main__":
    # machine to convert a string of A's and B's to
    # all A's and accept
    m = TuringMachine("ABBABB", [1])

    m.addTransition(0,'A',0,'A','R')
    m.addTransition(0,'B',0,'A','R')
    m.addTransition(0,'_',1,'_','L')

    # run the TM
    m.execute()

The Machine can loop forever like a real Turing Machine.

Created by Ryan Phillips on Wed, 3 Dec 2003 (PSF)
Python recipes (4591)
Ryan Phillips's recipes (1)

Required Modules

Other Information and Tasks