logoalt Hacker News

moi2388last Sunday at 5:06 PM3 repliesview on HN

Are they? Are there any actual Turing machines? Doesn’t that require infinite memory? I don’t know of a single thing which actually has that, nor one that comes close.


Replies

Chinjutlast Sunday at 6:40 PM

That just means even more limitations, then. (Though the grandparent comment is correct that literally everything is subject to the same Gödel-style limitation on its ability to make negative claims about its own behavior, whether computers, humans, or any other system at all.)

silver_sunlast Sunday at 10:18 PM

Not infinite memory, a Turing machine only requires "unbounded" memory, which is a way of saying that it will not run out of memory while running its program with the given input. In other words it just needs to have enough memory to run the program with whatever inputs it was given, which is much less than infinity. And this situation is quite common in the real world -- the programs I use on a daily basis have all the memory / RAM they need to do what I want (almost by definition). So in practice I might as well view them as Turing machines.

jiballast Sunday at 5:32 PM

Finite machines such as FSMs (finite state machines) are a subset of TMs, so yes they are actual Turing Machines. What they aren't is UTMs ... universal Turing Machines that can emulate every TM.