[FOM] Simple Turing machines, Universality, Encodings, etc.

[joeshipman@aol.com]

I thank Steven Wolfram for his extended response, which clarifies many 
things. I still have two questions for him.

What is the smallest TM you know of which has an r.e.-complete halting 
set of initial configurations that are nonzero in only finitely many 
cells?

Don't all reasonable finitely axiomatized axiom systems have proof 
lengths which differ by an additive constant? Once the shorter axiom 
system proves the axioms of the longer axiom system, it can do 
everything else the longer system can do with no additional penalty, so 
the most interesting question seems to be whether there are axiom 
systems (which might as well be single axioms if conjunction is 
allowed) which have proofs, but only long proofs, from shorter systems.

-- Joe Shipman

________________________________________________________________________
Email and AIM finally together. You've gotta check out free AOL Mail! - 
http://mail.aol.com