7 ms·

Here's an idea that I once had about how to visually determine if a program terminates or not: Convert a program to a Game of Life equivalent program. Observe

Here's an idea that I once had about how to visually determine if a program terminates or not: Convert a program to a Game of Life equivalent program. Observe if there are any run-away gliders. If there are, the original program doesn't terminate.

tupshin 9y ago
as long as execution is proceeding without generating any gliders, then you don't know whether gliders will be generated in the future. in addition, if you have gliders, you have no guarantees that another structure won't catch up to it and end its gliding.
- iainmerrick 9y ago
  Many gliders move at the theoretical maximum rate on the Life board, so it won’t be possible to catch them.
  - darkmighty 9y ago
    I believe c/4 is indeed the fastest possible diagonal speed for a spaceship, does anyone know if a proof exists?
    - dvgrn 9y ago
      Yes, there's a fairly simple proof, specific to the B3/S23 Life rule, not true for all similar CA rules. Unfortunately this comment box is too small to contain it... and the proof only applies to structures traveling through empty space. If you're allowed to have pre-existing live cells ahead of the glider, there are known "wires" that transmit information diagonally at 2c/3, easily fast enough to get ahead of a glider and stop it.
    - OscarCunningham 9y ago
      This blog post has a explanation of the proof. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/ http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...
mankyd 9y ago
This doesn't seem to account for internally contained gliders. I.e. ones that are produced and consumed continuously.
westoncb 9y ago
This may be a more general form of what you're describing: look for small parts of programs (which re-appear often in many programs) which are proven to never terminate; if any of those simple non-executing subprograms are found, the larger program also will never terminate.
- darkmighty 9y ago
  This is a valid method of deciding whether a program hangs. Another very simple approach is searching for global state recurrences (if your program goes back to exact same state at least once, and it is deterministic, then it never halts). Note this has no bearing on the Halting problem though (famously proven impossible). You cannot decide whether an arbitrary very complicated program halts -- it may do all sorts of weird stuff that doesn't involve any of the previous behavior (having necessary subfunctions never terminate or global recurrence) -- it could try counting up to infinity until a certain complicated binary function of the number is true, then you have to decide the truthiness of this arbitrary function. In general you face a self-referential problem: imagine you try deciding whether a program of size N halts if it runs for too long. You'd need a program (say of size K) that produces a function f(N) of maximum running time for programs of size up to N -- then you could just check whether a program runs for more than f(N) steps. But by definition your program cannot run for more than f(K) steps, thus it cannot output a number greater than 2^(f(K)). Thus your program can only decide finitely many instances, and is not an algorithm (instead it is a sort of compressed look up table). The proof of the Halting problem undecidability is more general, but uses similar self-referential arguments. I like to think of it this way: an algorithm is really a compressor function. It compressed an infinite set of (input->output) relations into a finite program. But some infinite sets are inherently incompressible -- think a string of random numbers -- and in particular the set of all programs. Incompressible (actually finitely compressible) sets must exist because otherwise you would have infinitely many different sets that are output of finitely many programs, which is obviously impossible (this is the pigeonhole principle).
  - Leszek 9y ago
    I like the idea behind your compression analogy, but it doesn't quite work. In particular, you assume the solution when saying that the set of all programs is incompressible. Indeed, there are programs which operate on the set of all programs, e.g. trivially "is the first bit of the program a 1". I think you're correctly proving that non-computable functions exist (though the proof needs to mention countable vs uncountable infinities I think, based on a power set over the input/output set), but you still need some sort of self referential statement to prove the halting problem.
nneonneo 9y ago
This is, I think, the moral equivalent of checking to see if the program has started executing a “while(1) ;” loop (e.g. by finding that the current instruction is a “jump $pc”, ignoring multithreading). Although it definitely proves that a program doesn’t terminate, the converse is not true - most “interesting” non-terminating programs aren’t just busy-looping infinitely, they’re just performing computations that happen to have no way of ending. Similarly, a Life machine might just sit there and push gliders around in a circle forever, without sending out an infinite stream.
falcor84 9y ago
I suppose that this depends on the formulation of the problem, but these gliders might make sense as outputs (side effects) independent of the main program, which itself would be expected to terminate.
jopsen 9y ago
you would have to prove to that the Turing complete part of your simulation doesn't construct a glider that has never been seen before and moves so fast that it catches and terminates the run away gliders. It only makes sense if a program encoding in game of life is reasonably efficient. I highly doubt that's the case. But sure, ideas could be adopted. Also having no runaway gliders is not proof of termination.
- PeterisP 9y ago
  No, we have mathematical proof that in game of life the known gliders (c/4 diagonally or c/2 orthogonally) are as fast as possible, there cannot be faster gliders.
  - oneeyedpigeon 9y ago
    But what about this new non-orthogonal glider that we're discussing?
    - OscarCunningham 9y ago
      A glider that moves n cells horizontally and m cells vertically can do so only every 2*(n+m) generations. So this glider is optimal, it moves (2,1) every 6 generations.
    - sushibowl 9y ago
      Sir Robin moves at (2,1)c/6, meaning 2c/6 (or c/3) in one direction and c/6 in the other. This is apparently the maximum speed possible at this slope.
    - PeterisP 9y ago
      It's not faster, so it can't ever catch the "default" gliders if it's sent out afterwards. If a glider is moving at the provably optimal speed, then nothing can be faster.

tupshin 9y ago

as long as execution is proceeding without generating any gliders, then you don't know whether gliders will be generated in the future. in addition, if you have gliders, you have no guarantees that another structure won't catch up to it and end its gliding.

iainmerrick 9y ago
Many gliders move at the theoretical maximum rate on the Life board, so it won’t be possible to catch them.
- darkmighty 9y ago
  I believe c/4 is indeed the fastest possible diagonal speed for a spaceship, does anyone know if a proof exists?
  - dvgrn 9y ago
    Yes, there's a fairly simple proof, specific to the B3/S23 Life rule, not true for all similar CA rules. Unfortunately this comment box is too small to contain it... and the proof only applies to structures traveling through empty space. If you're allowed to have pre-existing live cells ahead of the glider, there are known "wires" that transmit information diagonally at 2c/3, easily fast enough to get ahead of a glider and stop it.
  - OscarCunningham 9y ago
    This blog post has a explanation of the proof. http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-life-like-cellular-automata/ http://www.njohnston.ca/2009/10/spaceship-speed-limits-in-li...

mankyd 9y ago

This doesn't seem to account for internally contained gliders. I.e. ones that are produced and consumed continuously.

westoncb 9y ago

This may be a more general form of what you're describing: look for small parts of programs (which re-appear often in many programs) which are proven to never terminate; if any of those simple non-executing subprograms are found, the larger program also will never terminate.

darkmighty 9y ago
This is a valid method of deciding whether a program hangs. Another very simple approach is searching for global state recurrences (if your program goes back to exact same state at least once, and it is deterministic, then it never halts). Note this has no bearing on the Halting problem though (famously proven impossible). You cannot decide whether an arbitrary very complicated program halts -- it may do all sorts of weird stuff that doesn't involve any of the previous behavior (having necessary subfunctions never terminate or global recurrence) -- it could try counting up to infinity until a certain complicated binary function of the number is true, then you have to decide the truthiness of this arbitrary function. In general you face a self-referential problem: imagine you try deciding whether a program of size N halts if it runs for too long. You'd need a program (say of size K) that produces a function f(N) of maximum running time for programs of size up to N -- then you could just check whether a program runs for more than f(N) steps. But by definition your program cannot run for more than f(K) steps, thus it cannot output a number greater than 2^(f(K)). Thus your program can only decide finitely many instances, and is not an algorithm (instead it is a sort of compressed look up table). The proof of the Halting problem undecidability is more general, but uses similar self-referential arguments. I like to think of it this way: an algorithm is really a compressor function. It compressed an infinite set of (input->output) relations into a finite program. But some infinite sets are inherently incompressible -- think a string of random numbers -- and in particular the set of all programs. Incompressible (actually finitely compressible) sets must exist because otherwise you would have infinitely many different sets that are output of finitely many programs, which is obviously impossible (this is the pigeonhole principle).
- Leszek 9y ago
  I like the idea behind your compression analogy, but it doesn't quite work. In particular, you assume the solution when saying that the set of all programs is incompressible. Indeed, there are programs which operate on the set of all programs, e.g. trivially "is the first bit of the program a 1". I think you're correctly proving that non-computable functions exist (though the proof needs to mention countable vs uncountable infinities I think, based on a power set over the input/output set), but you still need some sort of self referential statement to prove the halting problem.

nneonneo 9y ago

This is, I think, the moral equivalent of checking to see if the program has started executing a “while(1) ;” loop (e.g. by finding that the current instruction is a “jump $pc”, ignoring multithreading). Although it definitely proves that a program doesn’t terminate, the converse is not true - most “interesting” non-terminating programs aren’t just busy-looping infinitely, they’re just performing computations that happen to have no way of ending. Similarly, a Life machine might just sit there and push gliders around in a circle forever, without sending out an infinite stream.

falcor84 9y ago

I suppose that this depends on the formulation of the problem, but these gliders might make sense as outputs (side effects) independent of the main program, which itself would be expected to terminate.

jopsen 9y ago

you would have to prove to that the Turing complete part of your simulation doesn't construct a glider that has never been seen before and moves so fast that it catches and terminates the run away gliders. It only makes sense if a program encoding in game of life is reasonably efficient. I highly doubt that's the case. But sure, ideas could be adopted. Also having no runaway gliders is not proof of termination.

PeterisP 9y ago
No, we have mathematical proof that in game of life the known gliders (c/4 diagonally or c/2 orthogonally) are as fast as possible, there cannot be faster gliders.
- oneeyedpigeon 9y ago
  But what about this new non-orthogonal glider that we're discussing?
  - OscarCunningham 9y ago
    A glider that moves n cells horizontally and m cells vertically can do so only every 2*(n+m) generations. So this glider is optimal, it moves (2,1) every 6 generations.
  - sushibowl 9y ago
    Sir Robin moves at (2,1)c/6, meaning 2c/6 (or c/3) in one direction and c/6 in the other. This is apparently the maximum speed possible at this slope.
  - PeterisP 9y ago
    It's not faster, so it can't ever catch the "default" gliders if it's sent out afterwards. If a glider is moving at the provably optimal speed, then nothing can be faster.