What is a Turing Machine?
A Turing machine can be described as a universal computing machine or a hypothetical machine (University of Cambridge). Invented by Alan Turing in 1936, the concept of the Turing Machine inspired Turing's invention of the Bombe and the first electronic computer, the Colossus. Both machines were used to break Axis codes in World War II. The Turing machine stressed the limitations of mechanical computing and highlighted the potential of electronic computing. The Turing machine operated on a memory tape. The tape was divided into cells (analogous to an array's elements) . Moving from left to right, the machine would check if it's current position had a symbol and executed the necessary operation given the state. However, like a good computer scientist, providing a formal description is not enough. Instead, demonstrating how a Turing machine works is one step closer to understanding its relation to lambda calculus.
Computer programmer and author of The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability, Charles Petzold, enlightens us with the inner-workings of Turing machines.
Figure 1.1
(The Annotated Turing, p. 84)
To understand the table, I've included a description below.
The machine is dependent on the configuration . The configuration includes m-config and symbol. The machine's operations are dependent on the symbol and state (m-config). An informal but simple way to understand the table above is by applying programming concepts to each column. For instance, m-config is the function name. The curly brace that encapsulates "None" to "1" represents if and else if statements. If the machine treks from left to right and sees no symbol anywhere on the tape, then we execute the operation for the symbol None. Petzold describes P0 as print 0. In this case, the machine will print 0. To illustrate this, I've included images below.
First, check if the current cell has a symbol.
There was nothing in the current cell. Then, the machine knows that the
symbol is "None" and will execute the operation P0 (print 0 ) .
Because the operation did not include the operation L (left) and R (right),
it does not move from its current cell.
The machine scans the current cell and executes the operation local to b
state and symbol 0. Hence, the current operation moves right 2 and prints 1.
Once it has moved twice to the right, the current cell is scanned and it finds no
specified symbol. Then, it executes the operation location to state b and symbol None.
Computers and Turing Machines
From the example above, why couldn't one relate computers to lambda calculus instead?
Given the definition and illustrations above, it is reasonable to say that a Turing machine (TM) is similar to a computer. Consider, both can compute the same function on numbers. For Turing machines, given a set of rules (like Figure 1.1) analogous to machine-code instructions of a computer, the TM can perform any computation. Furthermore, analogous to the central processing unit (CPU), the Turing machine's tape is like the machine's memory. Although, Turing describes the tape as infinite. There are no memory constraints. In this sense, A Turing machine is ideal for a model of a computer. A computer's inability to have infinite memory prevents it from being Turing complete. However, if the programmer implements an interesting program, instead of defining a computable function or a computable number, then a computer would be the best option.
Bubble Sort Example
To understand the relation between the two, the Turing machine's chart below performs a bubble sort just like any computer.
The table below is a state table where each row contains a 5-tuple; collectively they define the bubble sort algorithm for a Turing machine.
The tuples could be written more conventionally as
(1, 1, 1, 1, R), where R indicates a shift right, but are shown here as separate columns on each blue row. The first column contains the current state; the second column contains the value scanned by the head (blank, 1, 2, 3, 4, or 5); the third column contains the state to transition to; the fourth column contains the value to write ( also blank, 1, 2, 3, 4, or 5); the last column contains the operation to move the tape left or right or to not move at all. (Shift right, shift left, and stand still).
The states defined are 1, 2, 3, 4, 5, A, B, C, D, l , L , J, and z. (Note that the state between D and L is a little l not a 1.)
These states appear in columns one and three.
Here is an example of running the bubble sort on a Turing machine.
In this case, the machine will accept up to 5 digits (1, 2, 3, 4, 5) in some initial order. In this case the initial order is 5, 2, 3, 1, 4. The initial state is state 1.
The rule we are going to apply is as follows:
This could be expressed more conventionally as a tuple:
(1, 5, 5, 5, R).
We are in state 1 (first column is a 1, indicating state 1) and the head has scanned a 5 (column 2 contains a 5). The operation we are to perform is given by the 3rd, 4th, and 5th columns. The state we are going to transition to is state 5 as indicated in column 3. The value the head is going to write is 5 as indicated by column 4. Finally, we will shift the tape right as indicated in column 5.
The figure below shows the new state; note that the state is 5, a 5 has been written to the spot the head was scanning (which overwrote the 5 that was there already), and the head has moved to the right one as indicated by the grey over the cell holding 2.
At this point, the state is 5 and the current value scanned by the head is 2. So, the tuple for the next transition is as follows:
This could be expressed more conventionally as a tuple:
(5, 2, B, 5, L).
We are in state 5 (first column is a 5, indicating state 5) and the head has scanned a 2 (column 2 contains a 2). The operation we are to perform is given by the 3rd, 4th, and 5th columns. The state we are going to transition to is state B as indicated in column 3. The value the head is going to write is 5 as indicated by column 4. Finally, we will shift the tape left as indicated in column 5.
The figure below shows the new state; note that the state is B, a 5 has been written to the spot the head was scanning (which overwrote the 2), and the head has moved to the left one as indicated by the grey over the cell holding the first 5 from the left.
This process continues. For example at this point we note that we are in state B and the head scans a 5 (the grey cell). Eventually it will reach the end state with all the values in sorted order.
Note that the final state is z and all the digits are in sorted order. The last tuple executed before the end state is reached is shown below.
Note that an exclamation mark is written and the head stands still. (The exclamation mark appears in the grey square where the grey square indicates the current location of the head.) There are no tuples where the current state (column 1) is a z, meaning there is no transition from state z - it is the final state.
As addressed earlier, Turing machines are less complicated than computers. Relating Turing machines to lambda calculus is the more optimal choice.
Comparing Lambda Calculus and Turing Machines
At first glance, lambda calculus and Turing machines appear different and unrelated.
Before dismissing this possibility, examine what both entail. From the definition stated above for Turing machines, we know that it can compute the same function on numbers (like a computer) given a set of rules. Furthermore, it has an infinite amount of tape and executes the operations for each m-configuration. In comparison, lambda calculus expresses computation based on 3 programming constructs: abstraction, application, and variables (Kurz, Syntax of Lambda Calculus).
It adheres to the following rules:
Figure 1.2
(Wiki)
In addition, it has two reduction operations. For Alpha conversion, you can rename bound variables in the expression. Beta Reduction allows you to replace the bounds variables with the argument expression (Wiki).
Although their methods differ, the relation between the two is distinct.
In Turing's paper, "Computability and λ-Definability", he proves that λ-definable functions are computable by showing a Turing machine. Although his paper's purpose was to show that every λ-definable function is computable and that every computable function is general recursive (Petzold, p. 298), his use of a Turing machine to prove λ-definable functions shows that Turing machines are modeled after lambda calculus. This is indeed true. Alonzo Church's lambda calculus predated Turing's machine model and the Turing machine encapsulated key ideas from lambda calculus. However, a more distinct relation between the two is that they are equivalent models of computation. Meaning, computations in lambda calculus can be done in Turing machines and vice versa. To show that there are equivalent models of computation, it is not enough to say that a Turing machine can compute everything in lambda calculus, showing that both hold true then it is reasonable to say that these models are equivalent.
The untyped lambda calculus is Turing complete. (Typed lambda calculi are not Turing complete; here we consider only the simpler case of untyped calculi.) As such, any computation that can be performed by a Turing machine can be performed as well by the lambda calculus. The untyped lambda calculus can perform any computation the Turing machine can. In computability theory, equivalence between two theoretical models of computation means that they can solve the same set of problems. Since anything that can be computed with a Turing machine can also be computed using lambda calculus, then the two are equivalent.
Anything a Turing machine can do, the untyped lambda calculus can also do. The video below shows a hypothetical debate between the two.
Gotcha! :)
Must Reads/Watch
The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine by Charles Petzold
Turing Complete
References
University of Cambridge
Kurz, Syntax of Lambda Calculus
Wiki
Bubble Sort
Comentarios