Why don't we all chip in an buy Alan a computer so he can look stuff up
on Wikipedia.
Brent
On 8/22/2018 5:58 PM, John Clark wrote:
On Wed, Aug 22, 2018 at 8:26 PM, <[email protected]
<mailto:[email protected]>>wrote:
>>
Yes, the Busy Beaver Function is not computable. We know that:
BB(1) =1
BB(2) =6
BB(3) =21
BB(4) =107
*/
>
You haven't *written* the function, just its alleged values for
1,2,3,4. What is the function? /*
Starting with a all zero tape BB(N) is the number of operations any N
state Turing Machine performs after it writes the largest number of
1's and then halts. It is very important that it halt, some machines
will go on forever but they don't count. For example we know for sure
that BB(5) is at least 47,176,870 because one 5 state Turing Machine
has been found that halts after it goes through 47,176,870 operations
(and prints 4098 1’s on the tape), but there are 28 other 5 state
machines displaying non-regular behavior that are well past 47,176,870
operations and 4098 1's. If one of them eventually halts then that
larger number of operations will be BB(5), if none of them ever halts
then 47,176,870 really is BB(5); but the trouble is we'll never be
able to know it’s 47,176,870 because we'll never know that none of
those other 28 5 state machines will never halt because the Halting
problem is insolvable.
John K Clark
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to [email protected]
<mailto:[email protected]>.
To post to this group, send email to [email protected]
<mailto:[email protected]>.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
