FOM: Contest Announcement (note rule changes)

[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 (and also, I hope, to get a publishable
paper), I announce the following contest (the rules have been changed
slightly and the prizes increased to make the contest more attractive to
entrants):

TURING MACHINES AND INCOMPLETENESS CONTEST

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 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).  Such inputs are said to be
"standard inputs".

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
standard.


I will give a prize of $20 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 not win (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.

Winning entries will be incorporated in a joint paper to be submitted to
whatever journal seems most appropriate.

Prizes will be awarded May 8th.  If there is only one entry submitted in
a category no prize will be awarded.

"Matching" prizes are strongly encouraged!


-- Joe Shipman