On Sun, Jan 19, 2025 at 9:14 AM John Clark <johnkcl...@gmail.com> wrote:
> On Sat, Jan 18, 2025 at 2:45 PM Jesse Mazer <laserma...@gmail.com> wrote: > > *> my central point that Godel's theorem places no limitations on our >> ability to understand/predict dynamics over finite time periods, and that >> this is the sort of question physicists are almost always concerned with in >> practice* > > > *That's true but 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, but I see https://coopersnotes.net/docs/langmach/CHAP10%20Busy%20Beaver.pdf goes into detail and mentions that there are (4N + 4)^2N possible N-state machines for any given N), so 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? If intelligence in the universe were to find a way to perform computations forever with no upper bound on memory or number of computational steps (as in the speculative methods imagined by Freeman Dyson and Frank Tipler), then if you had a list of all possible Turing machines, the answer to the question of which of the first N machines halt and which don't wouldn't in general be computable (in the standard sense of being answerable by a program that's guaranteed to eventually halt and give you the final answer), but it would be "computable in the limit"--if you have a revisable output tape you can write down a tentative answer which you are free to update later, for instance you can run each of those N machines for a trillion steps and put a "1" in the slots of all the machines that have halted by then, and a "0" in the slots of all the machines that haven't. Then if you keep running the ones that haven't yet halted for more steps and get some additional halters, you can change the corresponding 0s to 1s on your output. There has to be some machine on your list that has the largest number of steps S to halt of all the machines on the list that halt at all, so if an intelligence keeps running all the programs for S steps or more than after that the answer on their revisable output tape will be correct and will never again change, but the intelligence will never *know* that S was sufficient so the answer they have written down is the final one (except in cases where they are able to find proofs for all the non-halting programs demonstrating that they never halt). By the same logic, 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 and that it wouldn't need to be updated in a future revision. I remember Schmidhuber made use of the notion of computability-in-the-limit when describing the measure he thought was most plausible for a mathematical ToE, mentioned for example at https://people.idsia.ch/~juergen/newai/node4.html Jesse -- 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 everything-list+unsubscr...@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/everything-list/CAPCWU3LNGeOuu9%2BwssDA0MJWjiO_5Wqx54fw8oAtQJ6cht9HYA%40mail.gmail.com.
