3 ms·

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 s

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.
- Pica_soO 8y ago
  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.
  - Dylan16807 8y ago
    > 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.

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.

Pica_soO 8y ago
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.
- Dylan16807 8y ago
  > 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.