Re:GIMPS Project Discovers Largest Known Prime Number
by schoen on Wednesday January 03, 2018 @04:39PM
(#16065454)
It's a little funny that mankind gets to use a full-fledged infinite-tape Turing machine in order to compute arbitrarily large computations, since no such machine would fit in our universe.
Re:GIMPS Project Discovers Largest Known Prime Number
by fooker on Wednesday January 03, 2018 @11:38PM
(#16068080)
The description of a Turing machine that can do arbitrarily large computations can be finite.
See: Kolmogorov complexity.
Re:GIMPS Project Discovers Largest Known Prime Number
by schoen on Thursday January 04, 2018 @12:34AM
(#16068288)
Sure, but it feels a little funny in one way to say that people "know" all of its output, although I'd agree that for other purposes being able to write a program to generate something is a relatively good description of what it means to understand it.
(Formally: the knowledge predicate is usually assumed to satisfy modus ponens: if mankind knows "A implies B" and mankind knows "A", then mankind knows "B")
Under this abstraction, if mankind knows the axioms of logic and Peano arithmetic, then mankind [ideally eventually] knows the primality of all primes.
Contrast: Which Turing machines will mankind [ideally eventually] know are never-halting? This is a much harder question and the answer is probably not "all never-halting Turing machines"