Hacker News new | ask | show | jobs
by kazinator 642 days ago
What? A Turing machine can literally be built. The only problem is supplying the infinite tape, or splicing on more when it runs to the end of a finite tape.

Machines that address storage using fixed width pointers (and have no other kind of storage) cannot be Turing machines.

1 comments

The only problem is supplying the infinite tape

In so far as infinite tape is feasibile, you are correct.

Any useful TM program halts, so you need finite tape. Only figuring out beforehand how much will you need is difficult.
You don't want your telephone exchange to halt. That's why the engineering marvel Erlang. "Engineering" being the key word. The Halting problem isn't a real problem. Just pull the power cord.
You want every call handled in finite time. It's not that there is an unending computation in a telephone exchange, but a series of finite tasks. You can call it corecursion, coinduction or something else co-.