[Date Index] [Thread Index] [FOM Postings] [FOM Home]

*To*: fom@math.psu.edu*Subject*: FOM: Contest Announcement (note rule changes)*From*: Joe Shipman <shipman@savera.com>*Date*: Mon, 02 Apr 2001 11:07:02 -0500*Organization*: Savera systems*Sender*: owner-fom@math.psu.edu

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

[Date Prev] [Date Next] [Thread Prev] [Thread Next]

[Date Index] [Thread Index] [FOM Postings] [FOM Home]