Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Largest provable BB(N)?
Replies: 12   Last Post: Oct 31, 2004 11:57 PM

 Messages: [ Previous | Next ]
 Daniel A. Jimenez Posts: 64 Registered: 12/12/04
Re: Largest provable BB(N)?
Posted: Oct 28, 2004 3:59 PM

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

Date Subject Author
10/28/04 Russell Wallace
10/28/04 Robert Low
10/28/04 Russell Wallace
10/28/04 Robert Low
10/28/04 tchow@lsa.umich.edu
10/28/04 Russell Wallace
10/28/04 tchow@lsa.umich.edu
10/28/04 Russell Wallace
10/28/04 tchow@lsa.umich.edu
10/28/04 Daniel A. Jimenez
10/28/04 Dennis Ritchie
10/31/04 Keith Ramsay
10/31/04 Keith Ramsay