3 ms·

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 h

by 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.
  - 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.

by 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.
- 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.