Hacker News new | ask | show | jobs
by skissane 1737 days ago
> I find the Turing Machine a much more intuitive model of computation than say lambda calculus

I think register machines are more intuitive than Turing machines - they are much closer to how real world computers work.

3 comments

But that's the opposite direction from Turing's intention. The point of the Turing machine model is for the machine to be both mechanically plausible (no magic required) but also equivalent to what a human does when performing computation.

The Turing machine model is a mechanically plausible abstraction of a human performing a computation by following some steps in their mind and with a notebook. The tape stands in for the notebook. The read head stands in for the human's eyes. The write head stands in for their pencil hand. The internal state of the machine stands in for their mental state. At every step, you either read a symbol from the notebook tape and change your mental state in relation to this symbol, or write a symbol based on the current mental state. The procedure itself can be written on the tape, and you can occasionally refer back to it.

The original paper spends a good few pages working out this metaphor and showing that the machine model perfectly abstracts the mathematician's work of computation.

Yes, on the abstract computation side of the link register machines are much more intuitive.

But on the physical side of the link they are much less intuitive IMHO: it’s much less clear that “this is just a machine that I could build in my garage”.

The Turing machine is definitely not some machine that you could build in your garage. None of the mechanisms are specified or even specifiable. The important part, to Turing ateast, is that it perfectly matches what a human does while computing a number, and that there are no magical steps like 'thinking'. Read symbol, change internal state, write other symbol down, rinse and repeat.

All of the details of how a symbol is read, recognized, how it alters the internal state, how the next symbol is chosen, or even how many symbols you actually need are not mentioned and even considered irrelevant. Turing wasn't building one of these, he was proving that this model captures all known computation, and that even so it is undecidable whether this machine would ever stop for any arbitrary computation.

No “the Turing Machine” isn’t a machine you can build in your garage. It’s an abstraction.

But any individual Turing machine is. Building a simple one is not very hard, and you can imagine supplying it with more and more tape as it needs it.

It’s thus the only model of computation that I can fully imagine “working”. And that to me is the beauty of Turing’s contribution.

The “physical side” was probably more important when Turing first came up with the idea, and people struggled to conceive of computers because none had yet been built. Nowadays it is arguably less necessary because they are an essential part of everyday life, and most people learn some programming before learning theoretical computer science.
In the days where you can buy a ram chip, a register machine is a really easy abstraction.

If you're trying to imagine something you can mechanically assemble out of discrete compoonents, it's not so great. You need an unlimited number of components hooked up in complicated ways.

A turing machine is a fixed-size and relatively simple box, plus a long tape that feeds through.