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