Re: Largest provable BB(N)?

From: Daniel A. Jimenez (djimenez_at_cs.utexas.edu)
Date: 10/28/04 

Date: 28 Oct 2004 14:59:01 -0500

In article <41812c38.278841778@news.eircom.net>,
Russell Wallace <wallacethinmintr@eircom.net> wrote:
>On 28 Oct 2004 16:24:12 GMT, mtx014@linux.services.coventry.ac.uk
>(Robert Low) wrote:
>
>>Not necessarily: it may well be that you can do it for
>>any particular N, but that there is no general procedure
>>which will do it for arbitrary N. Or even that for any
>>TM with N states there is a procedure, but no procedure
>>that will work on an arbitrary N-state TM.
>>
>>(I've no idea if this is the case, merely observing
>>that it's a logical possibility.)
>
>It is the case that for any particular TM, or any finite set of TMs,
>there is a formal system that will identify non-halting. (E.g. for any
>given TM, either the program PRINT "YES" or the program PRINT "NO"
>will do the job.)
>
>What I'm asking is: given the particular formal system "the most
>powerful set of mathematical tools known to present-day humanity" (is
>that Zermelo-Fraenkel set theory and derivations therefrom, or is
>there something more powerful?) what is the highest N for which all
>N-state Turing machines can be identified as halting/non-halting?
>
>Or to be more exact: I'm sure the exact N isn't known, so what's the
>best guess, that people who know more mathematics than I do, would
>give for what sort of figure it's likely to be?

It will depend on how many symbols the Turing machine can use. An upper
bound for N will be whatever the current smallest universal Turing
machine is. Marvin Minsky came up with a 4-symbol, 7-state universal
Turing machine; I don't know what the current smallest UTM is. 

-- 
Daniel Jiménez                     djimenez@cs.utexas.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
"                             " -- John Cage

Relevant Pages

  • Re: Largest provable BB(N)?
    ... >that Zermelo-Fraenkel set theory and derivations therefrom, ... >Or to be more exact: I'm sure the exact N isn't known, ... It will depend on how many symbols the Turing machine can use. ... bound for N will be whatever the current smallest universal Turing ...
    (sci.math)
  • Re: Probabilistic / Nondeterministic Turing Machines
    ... > but not all computers or all programming languages are the equivalent ... > of a Universal Turing Machine. ... I suspect the same is meant by "nondeterminism" in the other languages you ...
    (comp.arch.embedded)