Lagani Lagani - 1 year ago 79
Python Question

Can someone explain to me this Turing machine code?

I am newbie to Python so I don't really understand this. It's some kind of Turing machine that should write binary number, but I can't figure out what's going on after these rules

from collections import defaultdict
import operator

# Binary counter
# (Current state, Current symbol) : (New State, New Symbol, Move)
rules = {
(0, 1): (0, 1, 1),
(0, 0): (0, 0, 1),
(0, None): (1, None, -1),
(1, 0): (0, 1, 1),
(1, 1): (1, 0, -1),
(1, None): (0, 1, 1),
# from here I don't really understand what's going on

def tick(state=0, tape=defaultdict(lambda: None), position=0):
state, tape[position], move = rules[(state, tape[position])]
return state, tape, position + move

system = ()
for i in range(255):
system = tick(*system)
if(system[2] == 0):
print(map(operator.itemgetter(1), sorted(system[1].items())))

Answer Source

It is a state machine. At each tick a new state is computed based on the old state and the contents of tape at 'tape position' in this line:

state, tape[position], move = rules[(state, tape[position])]

This statement is a destructuring assignment. The righthand side of the assignment will give you an entry of rules, which is a tuple of three elements. These three elements will be assigend to state, tape [position] and move respectively.

Another thing that might puzzle you is the line:

system = tick(*system)

especially the *.

In this line the (processor clock) tick function is called with the contents of tuple 'system' unpacked into separate parameters.

I hope this is clear enough, but the fact that you're interested in a Turing machine tells me that you've got something with computer programming... ;)

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download