3 ms·
Turing machines are literally “a set of distinguishable states,” along with the tape, and the rules of the machine. There’s nothing about binary in the definiti
by krallja 2y ago
Turing machines are literally “a set of distinguishable states,” along with the tape, and the rules of the machine. There’s nothing about binary in the definition. Or electrons.
2-symbol machines happen to have the smallest possible useful alphabet. And, because of Turing completeness, you can always define a binary machine that emulates any other Turing machine.
The same thing happens with Church’s lambda calculus - there’s no binary, and no electricity required.
Computer Science doesn’t require a digital electronic computer; after all, neither Church nor Turing did, when they wrote their research.
- deleted 2y ago[deleted]
- javajosh 2y agoTuring used a metaphor that was appropriate to his time: a tape, an alphabet, and a machine that reads (and writes to) the tape. It is a simplified expression of real machines - but it does not capture the essence of the connection between physics and computer science, because it does not stress the core features of what are required for computation physically, and only presents a simple isomorphism for reasoning about any given computational machinery. Actually, it had been a while since I read "Computing Machinery and Intelligence" and he does, in fact, speak directly to these issues (distinguishability of states, support for N distinct states not just 2) in sections 3 and 5 [1]. And in fact he notes the arbitrariness of the "tape" formulation. I think my point remains, though, that "The Turing Machine" itself does NOT stress these points, picking only advantageously simple examples of distinguishable states, even if the paper does. 1 - https://redirect.cs.umbc.edu/courses/471/papers/turing.pdf https://redirect.cs.umbc.edu/courses/471/papers/turing.pdf