On Sun, Jan 19, 2025 at 11:18 AM Jesse Mazer <[email protected]> wrote:
*>> I think Alan Turing's Proof that there is no general solution to the >> halting problem and it's corollary that some things are true but >> uncomputable, is more relevant than Godel's theorem. In general there is no >> way to determine if a cellular automation, such as Conway's Game Of Life, >> will keep on growing forever, or start repeating itself, or die out >> completely; all you can do is watch it and see what it does, and you might >> need to watch it forever. * >> *And the first five Busy Beaver Numbers are 1, 6, 21 , 107 and >> 47,176,870, and we know for a fact that even if we had a mechanical >> computer that strictly followed Newton's laws and even if we had an >> infinite amount of time at our disposal, we will NEVER find the 745'th Busy >> Beaver Number even though it's well defined and it definitely exists. The >> same thing could probably be said about the sixth busy Beaver Number, >> although we are not certain about that, all we know for sure is that it's >> greater than 10^15. * >> > > *> I gather finding the Nth Busy Beaver number requires knowing whether > all possible N-state Turing Machines halt or not (I don't understand the > exact definition of N-state Turing machine,* > *A**n easy way to understand is to separate the program and the data in a Turing Machine. The data is on the tape and the program is on a series of cards that determine what state the Turing machine is in. You always start at card #1 and, depending on if you are reading a 1 or a 0 , that card tells you to print a one or a zero, move left or right, and the number of the card to read next. A N card Turing Machine has N states plus a halt state. (The information on the cards could have originally come from the tape but we’ll assume that step has already happened.) For a start let's look at a one card machine, there are 8 different actions a card could tell you to perform if you first read a zero on the tape :* *1) Write a 1 or a 0.* *2) Move left or right.* *3) Stay on card#1 (the only card) or halt.* *So there are 2^3=2*2*2 =8 things you can do if you read a zero. But there are also 8 things you can do if you first read a 1 on the tape, so there are 8*8= 64 possible one card (aka one state) Turing Machines. * *Now let’s look at a 2 card Turing Machine, if you’re currently reading 0 there are 12 things the first card could tell you to do; write a zero or a one, shift left or right, go to card 1 or card 2 or halt, 2*2*3= 12. And if you’re currently reading 1 there are also 12 things the first card could tell you to do*. *So there are 12*12=144 ways that the first card could be. However each of those 144 cards must be paired up with a second card, and there are also 144 things that the second card could tell you to do. So there are 144*144= 20,736 different 2 card (a.k.a. 2 state) Turing Machines. * *The general formula is there are (2 N s +1) ^ s N Turing machines with N states and with s symbols. A two symbol machine is the simplest and can do everything a machine with more symbols can do so if s=2 the formula for the number of 2 symbol N state (card Turing Machines) is [4(N+1)]^2N. * *So the number of Turing Machines increases exponentially with N, but that's not the Busy Beaver function, BB increases far far faster than exponentially, in fact BB increases faster than ANY computable function. Starting with an all zero tape, BB(N) is the number of moves a N state Turing machine makes while printing out the largest FINITE number of 1's before it halts. Some Turing Machines print out an infinite number of 1's because they never halt but they do NOT count, it must halt.* > *> the fact that they found the first five must mean that for all the > non-halting machines with 5 or less states, they were able to find proofs > that they never halt?* > *Yes. For several decades people suspected that the fifth busy beaver number was 47176870 because they found a five State Turing machine that after making 47176870 steps and printing 4098 1s it halted, but they weren't certain because there were 28 candidate five state (card) Turing machines that were still running and printed many more than 4098 1s and MIGHT eventually HALT. But one by one people were able to prove that they would never halt, the last one fell just a few months ago , so there's no longer any doubt, Busy Beaver six is 47176870. Turing never said you can never predict what a Turing machine will do, he said you can't always predict it .* > *> an infinitely long-lived intelligence with unbounded computing power > could have tentative answers to the Nth Busy Beaver Number such that for > any given N, there'd be some future date at which they'd have the correct > answer written down and would never change it subsequently, but they could > never actually know for sure that it was the final answer* > *Yes. You may suspect that some number is a Busy Beaver number but you'll ever know for sure, in the same way we suspect that Goldbach's Conjecture is true because computers have checked it to several trillion, but that's not good enough because there is an Infiniti of even numbers. * *John K Clark See what's on my new list at Extropolis <https://groups.google.com/g/extropolis>* iop -- 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 view this discussion visit https://groups.google.com/d/msgid/everything-list/CAJPayv1DudOT9%2B99mEJ3wxtPFMpg4KUaiXw5_Gq03pPXpVoEtg%40mail.gmail.com.
