In the same very productive paper, Turing also proves that deciding if an arbitrary program will output an infinite number of symbols, cannot be done in finite time. His proof is quite cognitively challenging, but Tom LeBlanc has a version that is easier to follow [2].
I also implemented one of his early examples, which prints the sequence
001011011101111...
A solution to this is described in table form:
![]() |
Turing uses very stylistic letters as notation, which are ironically not very computer-friendly |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
tape = {} | |
head = 0 | |
state = "b" | |
def R(): | |
""" Right """ | |
global head | |
head += 1 | |
def L(): | |
""" Left """ | |
global head | |
head -= 1 | |
def P(sym): | |
""" Print """ | |
tape[head] = sym | |
def read(tmp=None): | |
if tmp is None: | |
return tape.get(head, None) | |
else: | |
return tape.get(tmp, None) | |
def accumulating(): | |
global state | |
val = read() | |
if state == "b": | |
P("e"), R(), P("e"), R(), P(0), R(), R(), P(0), L(), L() | |
state = "a" | |
elif state == "a": | |
if val == 1: | |
R(), P("x"), L(), L(), L() | |
state = "a" | |
elif val == 0: | |
state = "q" | |
elif state == "q": | |
if val in [0, 1]: | |
R(), R() | |
state = "q" | |
elif val is None: | |
P(1), L() | |
state = "p" | |
elif state == "p": | |
if val == "x": | |
P(None), R() | |
state = "q" | |
elif val == "e": | |
R() | |
state = "s" | |
elif val is None: | |
L(), L() | |
state = "p" | |
elif state == "s": | |
if val is None: | |
P(0), L(), L() | |
state = "a" | |
else: | |
R(), R() | |
state = "s" |
I keep track of the tape using a dict. Both tape, head, and state are global variables.
Conclusions
Using a Turing machine is a very pure way of programming. That is to say, one works with an extremely small set of operations, and one needs to model every detail of the problem. It feels like building a house by starting collecting mud from the creek instead of buying bricks.
It is not an efficient way of programming, even if one would implement the operations directly in hardware. Modern hardware is better than being able to see a single symbol at a time. It is not efficient for the programmer either. It is tricky to debug and a hard way to model problems. The Turing machine mostly has value as a theoretical tool.
[1] On Computable Numbers (Turing 1936)
[2] Undecidability
Inga kommentarer:
Skicka en kommentar