Hacker News Reader

Comment by pcalderw | Hacker News Reader

In a memory bounded Turing machine, when we see that on step Y we repeated step X we also know that tape and header on step Y+1 will be identical to step X+1. This is because computation is entirely driven by the state of the tape, namely the symbols on the tape and where the head of the tape currently is located. It is fully deterministic. By induction, since it only took a finite number of steps (n) to go from X to Y again we know that at Y+n steps we will have repeated the computation loop.

While we could use programs that change their instructions based on the data, they are still equivalent to a Turing machine in power so they would be able to solve the halting problem with the restriction of finite memory.

View on HN

Yes, i know that proof by induction basically proofing that the program loops - the logic there holds.

But if you create what is basically a glider gun, calculating PI without every storing the numbers it works on and its results, it still will be busy indefinitely - so only from finite space, halting can not be proofen.

PS: Found the flaw in my thinking, even in such a stateless function - the numbers of the result would eventually get so big, they would fill the space on the tape, thus limiting computation, thus allowing to proof via size induction on the number that the program halts. Where there is computation, something needs storage, even if it is just a result.

I don't think you have the right point, even with an infinite write-only output tape, you'd still need infinite states to output pi. How can your machine know how far along it is otherwise?

The original thought was, that it wouldnt need to know, it would get the operands on a tail-call eliminated, recursive need to know basis- very slow, but very space efficient, basically lazy re-compute it every time its needed.

Still was wrong.

Even with tail calls, and purely functional code, it can be shown like this: imagine you see a purely functional, tail-called, all-state-as-argument call foo(A, B, REST-OF-STATE). Later on, you encounter the same call with exactly the same values - foo(A, B, REST-OF-STATE). At this point you know that the program looped, since you've proven (through observation) that the call to foo(A, B, REST-OF-STATE) will eventually yield another call to foo(A, B, REST-OF-STATE).

This is essentially equivalent to detecting cycles in a directed graph where each node has outdegree of 1. If you hit the same node twice, you've found a cycle.

It boils down to the question how dense you can encode, retrieve and write information- and this can be very dense.

Conways compression comes to mind, where a simple timing description and some start states can be used to describe a very complex outcome.

The problem is, that for every function computing a irrational number, you got to have the output as input again.

Imagine if it where otherwise, a completely lightweight PI-function, traveling for eternity, for which nothing in the universe could determinate if its going in a loop or going towards a circle constant.

> It boils down to the question how dense you can encode, retrieve and write information- and this can be very dense.

Your max density is 2^bits.

> Conways compression comes to mind, where a simple timing description and some start states can be used to describe a very complex outcome.

Eventually your 'time' number is so big it takes up the entirety of ram, and you can go no further.

Another way to see this is that a computer with limited memory can be modeled as a finite state machine. For every possible arrangement of memory and other internal state, you have a node. Include the finite input as part of the state too. If your computer is deterministic, every state leads inevitably to one next state.

If your computation runs infinitely and there are finite states it can hit, it must hit the same state twice. Since there's only one thing it can do from that state, it will just repeat the same thing it did on its first visit to the state and eventually come back. So the machine is in an infinite loop.

This is true even if you remove the output storage from your model. You could have external storage and label each state transition with what it writes to the output. This tells us that either the output is finite or it's periodic. The digits in an irrational number are not periodic, so a finite machine can only output all the digits in a rational number.

Reply on news.ycombinator.com