|
|
Re: Largest provable BB(N)?
Posted:
Oct 28, 2004 3:59 PM
|
|
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
|
|
