Fred Chen wrote:
>Sounds like you are going after some magic program that generates all
>possible programs. Would this program be a logical necessity in and of
>itself? That is, must it necessarily exist? Or would it just happen to
>exist?
It is a theorem that it exists a universal program able to generate
and execute all programs in all "existing" programming language so far
(from Babbage machine to the Deutsch universal quantum machine). With the
philosophical thesis of Church Turing Post Markov ..., that universal
program generates and executes *all* possible programs including the
futur programs written in futur language!
Because necessarily some programs will not stop, the only way to
execute all programs is by dovetailing; for exemple the UD (universal
dovetailer) generates the first LISP program, executes it a little bit,
then generates the second program, executes it a little bit, *then* goes
back to the first one, generates it a little further, etc.
See
http://www.escribe.com/science/theory/m2793.html for a universal
dovetailer written in LISP. Among the LISP programs you have all the
simulation of Fortran programs, Joel's minimal cellular automata, etc.
This is a consequence of the existence, discovered by Post and Turing
of universal machine/program.
Godel has considered Church thesis as a real epistemological miracle.
The set of programmable functions is closed for the diagonlisation.
(That is: diagonalisation of the set of programmable functions leads
to programmable functions). This is fundamentally what makes Church
Thesis consistent.
So the existence of the UD is logical necessity for all existing
programming systems (including the quantum one), and is made
philosophically "absolute" by Church thesis.
With Church thesis the universal Turing machine *is* the universal
machine *tout court*. And it exists necessarily by the math.
Bruno
Received on Fri Jun 29 2001 - 03:33:48 PDT