Turing machines

I want to dig deeper into the meaning of computation, and the limits of what programming can be. As part of that, I read through Turing's 1936 paper [1]. Turing defines a computable sequence as any sequence (possibly infinite) that is the output of a program of finite size. He goes on to describe a finite set of symbol manipulation operations that is sufficient to compute any computable sequence. This later became known as a Turing machine. The operations themselves can be assigned symbols, so a Turing machine can be designed to emulate other Turing machines, given only a description of the emulated machine as input. Such a system is called a Universal Turing machine.

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

My code for this:

	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"

view raw accumulating.py hosted with ❤ by GitHub

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