Hi Peter,
On 20 Jun 2016, at 13:14, Peter Sas wrote:
I have a question about the concept of the universal dovetailer. I
understand that the necessity to postulate the UD follows from the
Halting Problem (HP): since there are uncomputable functions from N
to N, and since because of the HP there is no algorithm for deciding
which functions are computable, we need a UD to dovetail all
possible functions zigzag-style.
Now my question is: Does this mean that the UD dovetails all
possible functions, including the uncomputable ones?
The UD dovetails on all partial computable functions, which correspond
always on algorithm. It does not dovetail on non computable functions,
which have no algorithm.
It executes all programs, on all inputs. It dovetails because, indeed,
some program will not stop, and we cannot be sure which one in advance.
Now, it will execute all programs on *all inputs*, including infinite
streams, and so the UD will dovetail also on the non computable
*inputs*, but only as input, not as executable code. So, it will not
dovetail on *all* functions, except in an indirect way when they are
seen as inputs or oracles.
Ask more if this is not entirely clear,
Best,
Bruno
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
