6 ms·

The most important machine that was never built

68 points by akeck 3y ago

KingOfCoders 3y ago
I think Hilbert is one of the most underrated - and unknown - people (outside experts).
- btilly 3y ago
  Agreed. Anyone who is curious about him should read the superb biography https://www.amazon.com/Hilbert-Constance-Reid/dp/0387946748 https://www.amazon.com/Hilbert-Constance-Reid/dp/0387946748. It is excellent both for understanding his life, and slips in the subtle philosophical points that he introduced to mathematics. (Like what mathematical existence should mean in his view.) And yet manages to be appropriate for a general audience with no knowledge of math. I know of no better explanation for a lay audience of where Formalism, the philosophy of math that most mathematicians officially subscribe to, actually came from.
tromp 3y ago
> Turing’s great insight was to provide a concrete answer to the computation question in the form of an abstract machine, later named the Turing machine by his doctoral adviser, Alonzo Church. It might be worth mentioning the lambda calculus that Alonzo Church had already introduced as an abstract model of computation. One that continues to have a profound impact on contemporary programming languages, such as Haskell. Turing's great contribution was showing how a Turing Machine could do everything that a human mathematician could work out on (arbitrary amounts of) paper.
- pulvinar 3y ago
  An aside: GPT4 added this comment after asking it about Alonzo Church: ...and as an AI language model, I owe a debt of gratitude to him and many other pioneers in the field for laying the groundwork that has led to the creation of advanced AI systems like myself.
  - checkyoursudo 3y ago
    > advanced AI systems like myself Aw, it is its own hype machine.
  - intelVISA 3y ago
    > advanced AI systems like myself hallucinations from the GPU powered lexer again?
- russdill 3y ago
  The insight that there are problems a theoretical machine with infinite capacity and infinite time cannot solve is such an interesting result.
tpmx 3y ago
Related: It's a crime that the mechanical Charles Babbage Analytical Engine (1837) hasn't been built. Just found this recent progress report on an effort to do just that (written by Doron Swade [https://en.wikipedia.org/wiki/Doron_Swade https://en.wikipedia.org/wiki/Doron_Swade], posted by HN user jgrahamc): https://blog.plan28.org/2023/03/spring-2023-report-to-computer.html https://blog.plan28.org/2023/03/spring-2023-report-to-comput... From https://en.wikipedia.org/wiki/Analytical_engine https://en.wikipedia.org/wiki/Analytical_engine: The analytical engine incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete. It don't think it gets much more steampunk than this in actual history.
- stavros 3y ago
  Jgc is also the CTO of Cloudflare.
  - jgrahamc 3y ago
    We are working on that. I am one of the people running Plan 28.
    - contingencies 3y ago
      Interesting project. If your goal is to attract contributors, consider adding an email address to the blog.
- niccl 3y ago
  If you haven't come across it, I recommend you check out 2D-goggles [0] for what might have happened... Sydney Padua is an animator and she's created some 3d animations of parts of the analytical engine. [1] [0] https://sydneypadua.com/2dgoggles/ https://sydneypadua.com/2dgoggles/ [1] https://sydneypadua.com/2dgoggles/uncategorized/the-marvellous-analytical-engine-how-it-works/ https://sydneypadua.com/2dgoggles/uncategorized/the-marvello...
nicole_express 3y ago
If you're interested in seeing a Turing machine in action, I really enjoyed this YouTube series where the creator builds a pure Turing machine that can simulate the Apple ][: https://www.youtube.com/watch?v=7hP4BTWvrGw https://www.youtube.com/watch?v=7hP4BTWvrGw Spoilers: it's, uh, not fast
leroy-is-here 3y ago
I think it is articles like this one which are misleading. The Turing Machine was never “built” because it is just a class of machines, i.e. particular machines are of the Turing Machine class, Turing-complete. Because the class of machine has an infinitely long “tape”, then finite machines can be created “under” it, or in that domain. Turing literally devised a method to create machines with a specific name, a number, and compute that number. Each and every one of your computers could be formalized to have a specific number, even if extremely large. Therefore, each of your computers are Turing Machines, unless of course you can show that you can run a program that the class of Turing Machines cannot. Edit: I think the surest example of this is in the term “binary”. When you compile a C program, you get an executable binary. Literally, you have a file of ones and zeroes. Well, that’s just an extremely large number in binary, exactly the same as the binary string “100001” being “33” in decimal.
- daniel-cussen 3y ago
  [dead]
- russdill 3y ago
  A Turing machine with a finite tape can be simulated with an FSM, and so is in a lower class.
  - leroy-is-here 3y ago
    I thought about your comment a lot and here’s a way, way better illustration: You are completely correct that we can formalize any Turing Machine as a FSM but! this _must_ include input. Again, this is just pure simulation as you state. Again, we can write a _single_ Turing Machine program with a _single_ input baked in as an FSM and that input _must_ be finite. But that FSM is not capable of handling _any_ input like the the Turing Machine it is simulating. That’s kinda the big difference between Turing machines and machines of a lower class. Any FSM has limited input thus limited states, but a Turing Machine can run infinitely with finite input. So, one can simulate the Turing Machine _with_ input using a FSM up to state N. But the actual Turing Machine can execute up to N+1 without having to hard-code any inputs and is capable of handling other inputs. Again, your computer is a Turing Machine capable of accepting Turing Machines as input. We can hard-code any individual programs and make them into a physical computer chip — just as we did with our computers which can accept any input it can handle, limited only by its physical limitations. But these physical limitations are not an indicator of it being of a lower class because we can keep pushing those limitations back and still compute more of states of these programs. Anyway, I’m glad you mentioned all of this because I went and pulled out my books.
deleted 3y ago
[deleted]

68 points by akeck 3y ago

KingOfCoders 3y ago

I think Hilbert is one of the most underrated - and unknown - people (outside experts).

btilly 3y ago
Agreed. Anyone who is curious about him should read the superb biography https://www.amazon.com/Hilbert-Constance-Reid/dp/0387946748 https://www.amazon.com/Hilbert-Constance-Reid/dp/0387946748. It is excellent both for understanding his life, and slips in the subtle philosophical points that he introduced to mathematics. (Like what mathematical existence should mean in his view.) And yet manages to be appropriate for a general audience with no knowledge of math. I know of no better explanation for a lay audience of where Formalism, the philosophy of math that most mathematicians officially subscribe to, actually came from.

tromp 3y ago

> Turing’s great insight was to provide a concrete answer to the computation question in the form of an abstract machine, later named the Turing machine by his doctoral adviser, Alonzo Church. It might be worth mentioning the lambda calculus that Alonzo Church had already introduced as an abstract model of computation. One that continues to have a profound impact on contemporary programming languages, such as Haskell. Turing's great contribution was showing how a Turing Machine could do everything that a human mathematician could work out on (arbitrary amounts of) paper.

pulvinar 3y ago
An aside: GPT4 added this comment after asking it about Alonzo Church: ...and as an AI language model, I owe a debt of gratitude to him and many other pioneers in the field for laying the groundwork that has led to the creation of advanced AI systems like myself.
- checkyoursudo 3y ago
  > advanced AI systems like myself Aw, it is its own hype machine.
- intelVISA 3y ago
  > advanced AI systems like myself hallucinations from the GPU powered lexer again?
russdill 3y ago
The insight that there are problems a theoretical machine with infinite capacity and infinite time cannot solve is such an interesting result.

tpmx 3y ago

Related: It's a crime that the mechanical Charles Babbage Analytical Engine (1837) hasn't been built. Just found this recent progress report on an effort to do just that (written by Doron Swade [https://en.wikipedia.org/wiki/Doron_Swade https://en.wikipedia.org/wiki/Doron_Swade], posted by HN user jgrahamc): https://blog.plan28.org/2023/03/spring-2023-report-to-computer.html https://blog.plan28.org/2023/03/spring-2023-report-to-comput... From https://en.wikipedia.org/wiki/Analytical_engine https://en.wikipedia.org/wiki/Analytical_engine: The analytical engine incorporated an arithmetic logic unit, control flow in the form of conditional branching and loops, and integrated memory, making it the first design for a general-purpose computer that could be described in modern terms as Turing-complete. It don't think it gets much more steampunk than this in actual history.

stavros 3y ago
Jgc is also the CTO of Cloudflare.
- jgrahamc 3y ago
  We are working on that. I am one of the people running Plan 28.
  - contingencies 3y ago
    Interesting project. If your goal is to attract contributors, consider adding an email address to the blog.
niccl 3y ago
If you haven't come across it, I recommend you check out 2D-goggles [0] for what might have happened... Sydney Padua is an animator and she's created some 3d animations of parts of the analytical engine. [1] [0] https://sydneypadua.com/2dgoggles/ https://sydneypadua.com/2dgoggles/ [1] https://sydneypadua.com/2dgoggles/uncategorized/the-marvellous-analytical-engine-how-it-works/ https://sydneypadua.com/2dgoggles/uncategorized/the-marvello...

nicole_express 3y ago

If you're interested in seeing a Turing machine in action, I really enjoyed this YouTube series where the creator builds a pure Turing machine that can simulate the Apple ][: https://www.youtube.com/watch?v=7hP4BTWvrGw https://www.youtube.com/watch?v=7hP4BTWvrGw Spoilers: it's, uh, not fast

leroy-is-here 3y ago

I think it is articles like this one which are misleading. The Turing Machine was never “built” because it is just a class of machines, i.e. particular machines are of the Turing Machine class, Turing-complete. Because the class of machine has an infinitely long “tape”, then finite machines can be created “under” it, or in that domain. Turing literally devised a method to create machines with a specific name, a number, and compute that number. Each and every one of your computers could be formalized to have a specific number, even if extremely large. Therefore, each of your computers are Turing Machines, unless of course you can show that you can run a program that the class of Turing Machines cannot. Edit: I think the surest example of this is in the term “binary”. When you compile a C program, you get an executable binary. Literally, you have a file of ones and zeroes. Well, that’s just an extremely large number in binary, exactly the same as the binary string “100001” being “33” in decimal.

daniel-cussen 3y ago
[dead]
russdill 3y ago
A Turing machine with a finite tape can be simulated with an FSM, and so is in a lower class.
- leroy-is-here 3y ago
  I thought about your comment a lot and here’s a way, way better illustration: You are completely correct that we can formalize any Turing Machine as a FSM but! this _must_ include input. Again, this is just pure simulation as you state. Again, we can write a _single_ Turing Machine program with a _single_ input baked in as an FSM and that input _must_ be finite. But that FSM is not capable of handling _any_ input like the the Turing Machine it is simulating. That’s kinda the big difference between Turing machines and machines of a lower class. Any FSM has limited input thus limited states, but a Turing Machine can run infinitely with finite input. So, one can simulate the Turing Machine _with_ input using a FSM up to state N. But the actual Turing Machine can execute up to N+1 without having to hard-code any inputs and is capable of handling other inputs. Again, your computer is a Turing Machine capable of accepting Turing Machines as input. We can hard-code any individual programs and make them into a physical computer chip — just as we did with our computers which can accept any input it can handle, limited only by its physical limitations. But these physical limitations are not an indicator of it being of a lower class because we can keep pushing those limitations back and still compute more of states of these programs. Anyway, I’m glad you mentioned all of this because I went and pulled out my books.

deleted 3y ago

[deleted]