[FOM] Simple Turing machines, Universality, Encodings, etc.
joeshipman@aol.com
joeshipman at aol.com
Sun Oct 28 19:32:52 EDT 2007
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
More information about the FOM
mailing list