3 ms·

I've often felt that neither Church nor Turing really captured the essence of computation. All you need is a set of distinguishable states, and the ability for

I've often felt that neither Church nor Turing really captured the essence of computation. All you need is a set of distinguishable states, and the ability for them to affect each other a la a nand gate. Neither binary nor electrons are particularly important to the idea. This is what's so great about these primitive machines is that they highlight the full generality of computation. I would like to see more non-binary systems though.

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 ago
  Turing 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
andoando 2y ago
A set of distinguishable states IS binary. You have something, and you have something else. Any more states can be broken down into binaries. It makes sense after all. If you have anything less than a binary then everything is the same, and the notion of tranformstions or things happening over time make no sense. It should be no surprise that binary/duality/positive negative/yin yang or whatever you call it is all over physics.

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 ago
Turing 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

andoando 2y ago

A set of distinguishable states IS binary. You have something, and you have something else. Any more states can be broken down into binaries. It makes sense after all. If you have anything less than a binary then everything is the same, and the notion of tranformstions or things happening over time make no sense. It should be no surprise that binary/duality/positive negative/yin yang or whatever you call it is all over physics.