3 ms·
> Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration. W
by teruakohatu 5y ago
> Which is what they do in FRACTRAN: they show how to encode an arbitrary program and its input as a number N, and how to read the output from the iteration.
What I don't understand is the encoding part. Is the encoding not essentially the same as execution? In other words the encoding function needs to be turning complete?
T(X) = N(E(T, X))
- romwell 5y agoEncoding is not the same as execution because you only encode the program and its input. You don't know what the output is unless you execute it on the FRACTRAN machine; the thing that gets you the output is execution. Note that execution is not a function that gives a finite output, as some programs never halt, or never return an output at all. So while you can always encode, you don't always get an output from that encoding (like in cases where the Turing machine never halts). TL;DR: encoding is a function (finite #of bits -> finite #of bits). Execution is a function (finite #of bits -> ???), where ??? can be a finite or infinite sequence, or an empty set, and there is no way to tell which it is other than executing, which may take infinite time (see: Halting problem).