Re:The Power of One-State Turing Machines (2018)
by watersb on Saturday November 23, 2019 @06:28PM
(#21617321)
I was going to point out a typo (more likely autocorrect).
But my head exploded, contemplating the awesome power of the "lambada calculus".
(I am revisiting SICP this month, you have profoundly affected my enjoyment of the Abelson-Sussman video lectures [2]. In a good way, I think.)
SICP: https://news.ycombinator.com/item?id=13918465
videos: http://www.youtube.com/playlist?list=PLE18841CABEA24090
So, once upon a time, Alan Turing needed a formal model of computation, as in what a mathematician could do to solve a problem with a sufficient supply of pencils and paper.[1] What Turing came up with is essentially a finite state machine attached to a "tape" which could read and write symbols and move left or right. (In the simplest model, the machine starts at one end of the tape, which is unbounded in the other direction.) There are two neat facts about this machine:
(1) The Turing machine is universal: you can construct a machine that takes as input a description of any other Turing machine and its input, and can perform the same computation as the other machine.
(2) You cannot do anything obvious to increase the power of the machine, as in constructing a machine that can compute something a Turing machine cannot. Examples: making the tape unbounded in both directions? Adding multiple tapes? A two-dimensional tape? Nope, all can be emulated by a standard machine. You can reduce the power of a Turing machine; remove the tape entirely and you have a finite state machine;[2] limit the use of the tape to the most recently written symbol and you have a stack machine.
(3) Turing machines are closely related to other, rather different, things. On one hand, those finite state machines are equivalent to regular languages, stack machines are equivalent to context-free languages, and Turing machines are equivalent to context-sensitive languages. On the other hand, Turing machines are equivalent to the other "reasonable" definitions of computation: general recursive functions and the lambada calculus, for example. In addition to not being able to extend the Turing machine for more power, all of the models of computation that are more powerful "cheat"; for example, being able to do an unbounded amount of computation in a single step.
For more details, see your local automata theory course.
[1] Turing needed the computation model because he wanted to know whether you could separate Gödel's unprovable sentences from normal-human-being, provable sentences. But that's not important right now.[3]
[2] Side note: All physically implementable computers are equivalent to finite state machines. But we generally hand-wave that away.
[3] You can't.