meekerdb wrote:
On 4/27/2015 7:34 PM, Bruce Kellett wrote:
I think it is appropriate to look more closely at the dovetailer. As I
understand it, the dovetailer calculates all computable functions over
the natural numbers: phi_i(x) = y where x and y are natural numbers.
In other words, phi_i is a map of the set of integers on to itself.
For example, the function phi(x) = x^2 +7 is one such function:
phi(1)=8, phi(2)=11, phi(3)=16, and so on.
So all that such a map does is establish a set of relations between
natural numbers: 1<->7, 2<->11, 3<->16, and so on.
As I understand it the dovetailer runs all possible algorithms, whether
they terminate or not. In fact one problem with idea seems be that the
measure of threads thru a particular state will be dominated by short,
non-terminating loops.
There is some confusion about exactly what programs the UD runs.
According to Bruno in SANE04, he takes the set N of all natural numbers,
defines a total function as a mapping from N to N, and computable if
there is a program which computes it. Then he says that P_k(n) is a well
defined number for each n (because the functions are total).
The in COMP(2013) we have "A 'universal dovetailer' (UD) is a program
that generates all the codes of the partially-computable functions phi_i
from N to N, and computing all such functions on all its arguments. In
other words, it is an algorithm that generates all other algorithms."
Russell, however, in his paper "The MGA Revisited", the universal
dovetailer effectively executes all possible computer programs, on all
possible inputs, albeit with exponential slowdown.
Now, in his recent reply to me Bruno claims that the UD "It is not a map
from N to N. But it is a map from N to N^N, limited to the partial
computable part of N^N. Here A^B represents the set of functions from B
to A). phi_i is a map from N to the maps of the set of integers on to
itself."
I think that at this point one is entitled to be a little confused as to
what is actually going on. It seems that perhaps the dovetailer first
generates all these programs, and then evaluates them for all possible
integer inputs.
This is then nothing more than, as I point out, the set of all maps from
N to N, which reduces to the sums of all possible sets of integers or,
even more simply, basic counting. All the algorithms can be boiled down
to steps that amount to no more that adding 1 to the previous result. y
= s(x) = x+1.
Now it remains for Bruno (and others) to prove that this is rich enough
to generate anything (everything!) Paraphrasing Bruno, it is all
contained in arithmetic.
Bruce
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
