Re: Largest provable BB(N)?
From: Dennis Ritchie (dmr_at_bell-labs.com)
Date: 10/29/04
- Next message: Rex Butler: "Classification Theorems for Banach Spaces?"
- Previous message: robert j. kolker: "Re: Infinity is not that big!"
- In reply to: Daniel A. Jimenez: "Re: Largest provable BB(N)?"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 29 Oct 2004 00:54:42 -0000
"Daniel A. Jimenez" <djimenez@cs.utexas.edu> wrote in message news:clrj25$n2g$1@keel.cs.utexas.edu...
... [first quoting]
> > ....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.
Shannon showed how to convert any TM into a 2-state TM.
As I recall there is only a polynomial growth in the symbol
set during the encoding. So N=2. I don't know whether
Minsky's |S|*|N| product has been improved.
Dennis
- Next message: Rex Butler: "Classification Theorems for Banach Spaces?"
- Previous message: robert j. kolker: "Re: Infinity is not that big!"
- In reply to: Daniel A. Jimenez: "Re: Largest provable BB(N)?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
