Science Talk

David Bernier · Guest

For Turing machines that start with a blank tape, there is the Busy
Beaver problem, which asks for the maximum number of '1's left on an
N-state Turing machine (blank tape at start) that halts.

For 5 states, Marxen and Buntrock found TM's that halt leaving
~ 4098 '1's.

We could say that a positive integer M is "5-state incompressible"
if any Turing machine starting with a blank tape that leaves
M '1's has 6 or more states.

By enumeration of types of 5-state TM's, among 100-digit numbers,
at least one is "5-state incompressible". And so on going down
to 99, 98, ... 12 digits (approximately). If the Busy Beaver
function Sigma, evaluated at 5, gives 4098, then
5000 is a "5-state incompressible".

"Some four-digit number is 5-state incompressible" (?)
This may be true and provable, but how short a proof is
not clear.

If we change from 5-state to 1000-state TM's, some
1000000-digit number is 1000-state incompressible (enumeration).
And so on down to numbers with ~ 7000 digits
(not enough TM's with <= 1000 states).

Somewhere between 1000 digits and 7000 digits, say
around 4000 digits, it will be hard to decide:
"Some 4000-digit number is 1000-state incompressible" (?)

If it's true, we replace 4000 by 3999 and so on.
Suppose at 2799 digits it's false, but 2800 digits it's true.

"Some 2800-digit number is 1000-state incompressible" (suppose true)
Which one? say X -->
"X is 1000-state incompressible" (suppose true)
Suppose this is undecidable in ZFC.

"Some 2810-digit number is 1000-state incompressible"
(Suppose true and ZFC-provable).

Going from 1,000,000 digits down to 7000 and then
2810 digits, asserting some k-digit number is
1000-state incompressible gets harder ( k = 1,000,000 ,
7000, ... 2810, ... 2800). Eventually, at 2800 digits,
it's independent of ZFC. Actually, by formulating it as:

"Some number with <= 2810 digits is 1000-state incompressible",
we get stronger and stronger statements when replacing
'2810' by '2809' and so on by decreasing by 1 each time.

It's also possible to select a range other than:
[10^{k-1} , 10^k -1], e.g. [a*10^{k-1}, b*10^{k-1}]
with a = 1997/1000, b = 2009/1000.

Perhaps some at least mildly interesting result only has
very long proofs [ results on particular decimals of pi
wouldn't count]. And I believe Con(ZFC) is not provable
in ZFC if ZFC is consistent. Before Russell's paradox and
Hilbert's program, I don't know if people thought of
consistency questions.

David Bernier

Gerry Myerson · Guest

In article <v7lck.4532$SR5.462@wagner.videotron.net>,
David Bernier <david250@videotron.ca> wrote: