[FOM] universal machine as a primitive instruction

[Tucker J.V.]

Colleagues,


1. It is not difficult to show that the primitive recursive functions have a total computable universal function but that it cannot be primitive recursive.

2. The importance of universality emerged in early papers by Hartley Rogers on enumerating the partial recursive functions that inspired A I Mal'cev to create the theory of numerations. The study classifies different enumerations and seeks axioms from which to derive theorems. Particularly impprtant are the s-n-m property and universality from which all sorts of results follow. The theory of numerations has a number of forms when applied to the partial recursive functions. One thinks of the programming systems of Machtey and Young's nice text book:

Michael Machtey and Paul Young, An introduction to the general theory of algorithms. North-Holland, New York, Oxford, Shannon, 1978, vii + 264

where elementary axiomatic style proofs of the Halting Problem and Rice's Theorem etc are derived from very simple axioms on enumerations.

3. The questions about the partial recursive functions are best answered by thinking axiomatically. Universality is an important axiom in the general axiomatic analysis of computation theories in:

Jens E. Fenstad, General Recursion Theory: An Axiomatic Approach. Perspectives in Mathematical Logic, Volume 10. Berlin: Springer-Verlag, 1980. 225 pp.

These computation theories unify a great deal of the basic properties of classical, abstract algebraic and higher type theories.

4. The axioms for computation theories have minimal models, namely the partial recursive functions.

5. The minimal model of a computation theory over a universal algebra is the class of partial functions definable by while programs with arrays or, equivalently, register machines with arrays, over the universal algebra:

J Moldestad, V Stoltenberg-Hansen and J V Tucker, Finite algorithmic procedures and computation theories, Mathematica Scandinavica, 46 (1980) 77-94.

John



________________________________
From: fom-bounces at cs.nyu.edu [fom-bounces at cs.nyu.edu] on behalf of David Leduc [david.leduc6 at googlemail.com]
Sent: Monday, April 15, 2013 2:40 PM
To: Foundations of Mathematics
Subject: Re: [FOM] universal machine as a primitive instruction

On Fri, Apr 12, 2013 at 10:51 AM, <T.Forster at dpmms.cam.ac.uk<mailto:T.Forster at dpmms.cam.ac.uk>> wrote:
Have i missed answers to this?

No, unfortunately you have not.

Is Turing-computable the only notion of computability that supports a universal machine?

At least in my textbooks and on Wikipedia, there is no weaker notion of computability that is shown supporting a universal machine. But can it be proven?


On Sat, Apr 13, 2013 at 11:40 AM, Steve Stevenson <steve at clemson.edu<mailto:steve at clemson.edu>> wrote:
I have my undergrad computability students, all computer science/math majors, implement emulators (universal machines) for FSA, PDA, and Tm  (both deterministic and non-deterministic) in their favorite programming language.

The way I understand "universal machine", it cannot be implemented in your favorite language but has to be implemented in the language of the machine it emulates.
[https://mail.google.com/mail/images/cleardot.gif]


-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20130415/4b82cf1e/attachment.html>