FOM: Contest proposal

[Joe Shipman]

What is the smallest object to transcend a given formal system?

If we can make the above question precise, we can get concrete results
that will allow us to compare formal systems in terms of their
algorithmic information content a la Chaitin.  The key is to pick a
reasonable "computational base" which will be regarded as zero-cost, so
that we can measure the size of objects "on top of" that base.

In order to stimulate research, I propose the following contest:

PROPOSAL -- NOT OFFICIAL UNTIL I HAVE SEEN COMMENTS AND SUGGESTIONS FOR
IMPROVEMENTS -- FINAL VERSION OF THE RULES WILL BE POSTED APRIL 2:

The computational base will be "2-dimensional Turing machines".  This
avoids the nasty coding issues that plague Turing machines with a fixed
number of tapes, and gives a system whose computational speed is
actually proportional to that of real computers.

A n-state m-symbol 2-dimensional Turing machine is specified by a set of
"quintuples" which are elements of

{0,1,2,...,n-1} x {0,1,2,...,m-1}x{0,1,2,...,n-1} x
{0,1,2,...,m-1}x{'Left','Right','Up','Down'}.

The names of the elements of a quintuple are (State, ScannedSymbol,
NewState, WrittenSymbol, DirectionToMove).

The first two elements of a quintuple represent "inputs" and the last
three of which represent "outputs".   The "tape" is actually a
2-dimensional grid.

There is a distinguished "initial" state numbered 0.  There is a
distinguished "blank" symbol numbered 0.  Computations start in the
initial state and all but finitely many squares in the grid contain the
blank symbol.

There is no special "halt" state; rather, the machine halts when there
is no quintuple whose first two elements correspond to the current State
and the current ScannedSymbol.  Thus if the machine is started on a
blank grid and there is no quintuple of the form (0,0,*,*,*) it halts
immediately.

A 2DTM is "deterministic" if no two quintuples have the same first two
elements.  Otherwise it is "nondeterministic".

The size of a 2DTM is the number of quintuples.

A 2DTM M has "input n" if, in the initial state, all squares are blank
except for a horizontal string of n consecutive 1's , and M is scanning
the square immediately to the left of that string.  Thus a completely
blank grid corresponds to input 0.

A deterministic 2DTM M calculates the partial recursive function f(n)
iff:

1) When f(n) is undefined, M fails to halt on input n.
2) Otherwise, M halts with its "head" on a cell immediately to the left
of a string of f(n) 1's, which is immediately to the left of a cell with
some symbol other than 1.  There is no requirement that the rest of the
grid be blank.

Note that *every* deterministic 2DTM computes some partial recursive
function.  If on input n the machine halts with the cell to the right of
the head having some value other than 1, then f(n)=0.  The function
computed by machine M is written f_M(n).  Even if this is a total
function, it is still possible for M not to halt on inputs that are not
of the form "all squares are blank except for a horizontal string of n
consecutive 1's , and M is scanning the square immediately to the left
of that string".


I will give a prize of $10 (but see CAVEAT below) to the best entry
received by May 1, 2001 in each of the following categories:

For deterministic 2DTM's:
1) Smallest M such that the statement "f_M is total" is independent of
PRA (Primitive Recursive Arithmetic)
2) Smallest M such that the statement "f_M is total" is independent of
PA (Peano Arithmetic)
3) Smallest M such that the statement "f_M is total" is independent of
ZF (Zermelo-Frankel Set Theory)
4) Smallest (M,n) such that the statement "f_M(n) is undefined" is
independent of PA
5) Smallest (M,n)  such that the statement "f_M(n) is undefined" is
independent of ZF
6) Smallest M such that an oracle for the halting behavior for M on
arbitrary inputs solves the halting problem [this includes inputs not of
the standard form, in order to make the construction of a universal 2DTM
easier].

For nondeterministic 2DTM's:
7) Smallest (M,n) such that the statement "M has no halting path on
input n" is independent of PA
8) Smallest (M,n)  such that the statement "M has no halting path on
input n" is independent of ZF

In categories 4,5,7, and 8 (M1,n1) is "smaller than" (M2,n2) if M1 is
smaller than M2 or M1 is the same size as M2 and n1<n2.

Entries must be accompanied by proofs.  If I cannot understand the
proof, the entry will be ineligible (unless someone on the FOM board
wishes to volunteer their services as a referee and can vouch for the
proof).  For categories 3, 5, and 8 entrants may assume whatever large
cardinal assumptions they need.

CAVEAT:  Prizes will be awarded May 8th.  If in the intervening week I
can improve on the best entry in a particular category, the prize in
that category will be halved.  This is to encourage entrants to
carefully refine and improve their entries before sending them in.

"Matching" prizes are strongly encouraged (the caveat will not apply to
matching prizes contributed by people other than me)!

END OF PROPOSAL

Please comment!

-- Joe Shipman