0
$\begingroup$

I am learning about computational models, I wonder why Turing chose his model of Turing machines (the strip with the head and Read / Move left or right / Change state). I am suspecting his physical machine Enigma was having a stripe and behaved similarly. Is this correct?

The circuit gates model seems close to what an electronic circuit can do (and seems more natural?), why aren't we using it?

If the two models are equivalent (are they?), then we can just use the simplest ? Why then is the Turing machine model more simple than the other models?

$\endgroup$
1
  • $\begingroup$ Did you read Turing's original paper? It is very readable and it explains carefully what the significance of the model is. $\endgroup$ Commented Jul 21, 2023 at 8:29

2 Answers 2

2
$\begingroup$

It's important to understand that the field of "computability", together with its vocabulary and formalisms, wasn't a thing in Turing's time.

Also, when introducing his machines, he was not trying to come up with a "computer architecture" in the sense understood today, planning a machine that you can build for problem-solving purposes.

Turing was intersted in a meta-mathematical problem that can be roughly stated as: what can a mathematician "solve" in a way that doesn't involve any insight or leap of creativity?$^1$

In his original 1936 paper describing these machines, he dedicates a third of section 9. ("The extent of the computable numbers - (a)") to justifying his "design choices":

He imagines a human trying to solve some mathematical problem, on a typical "child's arithmetic book", with the page divided into squares:$^2$

  • the "pages" are irrelevant, simply glue them all side by side to have just one long page
  • the "lines" are irrelevant, cut the page and glue the lines side by side to have a really long line
  • if you reach the end, buy another notebook, glue it to the end of your current one then keep going; similarly for if you reach the beginning$^3$
  • the symbols that can be written in a square must be distinguishable, so their difference can't be arbitrarily small; hence, a finite number of symbols
  • the number of observable symbols must be bounded - you can't notice everything at once; you can then straightforwardly argue that if there's a finite bound $B$, you could just as well reduce it to 1; thus a RW head placed over one symbol
  • when you're working on the problem, you operate in steps; at any step you can make a decision based on only two factors: what you're observing and what you're thinking, some "mental state";
    • you can choose to write something new; you can choose whether to read on, but you can't just jump with your eyes to some arbitrary point, you wouldn't know where to land; you can only go in a near place to the left or to the right (again, you can straightforwardly argue that you can reduce this to just 1 position L/R); finally you can choose to change your mental state. Hence, you get the transition function of a Turing Machine
  • like the symbols used, he argues that mental states must be finite.

From these principles, the Turing Machines follows naturally. Other computational models (e.g. Gödel's recursive functions, Church's lambda calculus) also aimed at answering this question, of what can be resolved "algorithmically"; they were trying to synthesize a vague, intuitive and imprecise philosophical concept as a rigorous mathematical formalism.

Turing's machines were the most compelling; it was the most successful at convincing people that the set of things computable by a Turing machine is indeed the sought-for set of "effectively calculable" things. The fact that other models with the same aim could be formally proven to "compute" exactly the Turing-computable things, served to further cement this idea; that "effectively calculable" is "Turing computable".


$^1$ The term used for such tasks was "effectively-calculable"; I recommend reading the first section of the SEP entry on the Church-Turing thesis for more background.

$^2$ You also need to adopt the convention that you write one symbol per square; so no large "m" taking two squares.

$^3$ It's very important, IMO, to understand that a Turing Machine doesn't require "infinite" amounts of tape; in fact, at any point $i$ of computation, at most $i$ squares can be non-blank, always a finite number; you just need "an arbitrarily large number"

$\endgroup$
1
$\begingroup$

The Turing machine is a very simple concept, based on two components: the program (a finite state machine) and an infinite memory (the strip). The FMSs were well-known at the time of Turing, as were the pushdown automata (a refinement of the former). Replacing the stack (of the SA) by a strip increases the power of the machine to an extent considered as sufficient to represent any imaginable computation. (Technically, a Turing machine can handle non-context-free grammars.)

Enigma does not have the power of a Turing Machine and AFAIK, has little in common. It is quite ad-hoc to break the encryption method used by the Germans.

The Turing Machine is a theoretical tool with a sound mathematical representation, which is much more compact and convenient to handle than logical circuits can be. In particular, it is not tied to the binary basis and does not need any diagrammatic routing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.