4 ms·

- The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a

- The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. Are you sure on that one? A system with finite memory can computate procedural, fractal, infinite equations and as long as it looses the state it started from - progress infinitely on this way back and forth. Thus even a limited system can computate eternally, and a program to proof this to be a correct program with a finite holding state, will follow this eternally into the abyss of computation.

TeMPOraL 8y ago
I think memory includes all program state, so at some point in the fractal computation you're bound to hit a memory state you've seen before - and since that state contains all that determines the program evolution, you can stop here and say that it won't finish.
- Pica_soO 8y ago
  Im sorry, but that seems.. unsound.. If i remember Cantors infinity theorem correctly, you can recombine sets to basically proof that the resulting set is bigger then the original sets. Now the naive assumption is that to recombine a set, you have to have the original sets "stored" somewhere. But assuming you have enough computation time, you can travel lightly - aka have tail-call eliminated recursive threads go back to the origins of such a set, following a formula and recompute both the values. Thus, you could have infinite reasonable work to do, with finite computation power?
  - pcalderw 8y ago
    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.
    - Pica_soO 8y ago
      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.
      - hcs 8y ago
        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?
        Pica_soO 8y ago
        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.
        TeMPOraL 8y ago
        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.
  - knappa 8y ago
    No it isn't unsound, it is an application of the pigeonhole principle. A finite memory and finite set of states implies that there are some finite number of configurations (call it N) that the computer can be in. Once you let the computer go N+1 steps, there must be at least one repeated configuration; which might be halting or not.

TeMPOraL 8y ago

I think memory includes all program state, so at some point in the fractal computation you're bound to hit a memory state you've seen before - and since that state contains all that determines the program evolution, you can stop here and say that it won't finish.

Pica_soO 8y ago
Im sorry, but that seems.. unsound.. If i remember Cantors infinity theorem correctly, you can recombine sets to basically proof that the resulting set is bigger then the original sets. Now the naive assumption is that to recombine a set, you have to have the original sets "stored" somewhere. But assuming you have enough computation time, you can travel lightly - aka have tail-call eliminated recursive threads go back to the origins of such a set, following a formula and recompute both the values. Thus, you could have infinite reasonable work to do, with finite computation power?
- pcalderw 8y ago
  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.
  - Pica_soO 8y ago
    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.
    - hcs 8y ago
      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?
      - Pica_soO 8y ago
        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.
        TeMPOraL 8y ago
        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.
- knappa 8y ago
  No it isn't unsound, it is an application of the pigeonhole principle. A finite memory and finite set of states implies that there are some finite number of configurations (call it N) that the computer can be in. Once you let the computer go N+1 steps, there must be at least one repeated configuration; which might be halting or not.