News for hackers. Stuff that matters.
Re:Why Philosophers Should Care About Computational Complexi... by hcs on Saturday July 21, 2018 @09:43AM (#17581949)
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?
Re:Why Philosophers Should Care About Computational Complexi... by Pica_soO on Saturday July 21, 2018 @12:50PM (#17582620)
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.

Re:Why Philosophers Should Care About Computational Complexi... by TeMPOraL on Saturday July 21, 2018 @01:13PM (#17582715)
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.

Re:Why Philosophers Should Care About Computational Complexi... by Pica_soO on Sunday July 22, 2018 @05:04AM (#17585924)
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.

Re:Why Philosophers Should Care About Computational Complexi... by Dylan16807 on Sunday July 22, 2018 @05:34AM (#17586001)
> 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.