Public

With this algorithm that optimally solves all well-defined problems, it's time to turn our attention to

*ill-defined*problems - which are, in fact, what I already specialize in.Abstract: An algorithm M is described that solves any well-defined problem p as quickly as the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms. M optimally distributes resources between the execution of provably correct p-solving programs and an enumeration of all proofs, including relevant proofs of program correctness and of time bounds on program runtimes. M avoids Blum's speed-up theorem by ignoring programs without correctness proof. M has broader applicability and can be faster than Levin's universal search, the fastest method for inverting functions save for a large multiplicative constant. An extension of Kolmogorov complexity and two novel natural measures of function complexity are used to show that the most efficient program computing some function f is also among the shortest programs provably computing f.

View 27 previous comments

- >you can ask if Goldbach's conjecture is true - that's a yes-or-no question

You consider that a well-posed mathematical question with a Yes or No answer?Aug 15, 2012 - +Toby Bartels - if the machine laughs at me I guess I won't.Aug 15, 2012
- By the way, in practice I feel confident that Goldbach's conjecture is true and suspect it will be proved in this century, thanks to the rapid progress we're seeing. I hope y'all saw this post:

https://plus.google.com/u/0/117663015413546257905/posts/KpBBoQzTtDG

where in a comment Richard Helfgott confirms that at this point, it's just a matter of buying enough computer time to complete a proof of the**weak Goldbach conjecture**, which says that every odd number greater than 7 is the sum of three odd primes.Aug 15, 2012 - +John Baez & +Daniel Lemire Having only read the comments I am now an expert on the field. Thus I am not sure how relevant what I write below is to any of this.

The way we currently practice science seems to naturally provide the interface between the human and the genie. Experimentalists constantly ask the genie all sorts of yes and no questions with at least some engineering success. This is one method of finding what questions to ask. Example do copper oxide compounds superconduct? With the answer YES "we" can then use this new fact to do other things, based on what we need and know already (example Maglev trains). What we can't do is say why (or even figure out what is the best sequence to use the new fact to optimize development or understanding). We'd have to break the "why" question down into many "smaller" binary one's (i.e., with yes or no answers) that can sequentially build us up from where we are to an answer we can understand. Then this new fact is feed back into the system of questions to do new things such as to get new facts and build new equipment or a compatible set of rules giving us the sensation that we are massively cross-checking the genie's answer (even when we are yet to ask it that particular question for which we think we already have an answer). Thus the questioner and the genie creates this scientific loop.

Another question experimentalists ask is "how much" in a yes or no form. A lot of physics is about asking how much and uses techniques in math to count how many of some unit (related to some fuzzy concept). How much of our questions can be put in such binary language, I don't know, but I vaguely remember glancing something along the lines that we cannot express all of our questions in binary (yes & no). I suppose someone will know more on this ghost memory of mine.

In this regard I don't see anything qualitatively repulsive about the description of the work. Perhaps sooner rather than later I would get the time to read the PhD thesis provided in one of +Alexander Kruel many links to get started and see what interest it holds for me. But no one (other than John) can read all the links (and the links' links) in John's post and (still) not be John. I hope this uninformed comment is not too far of the mark.Aug 16, 2012 - +John Baez, no I didn't see that post from May! So at least the weak Goldbach conjecture is (or has been reduced to) a well-defined mathematical question with a Yes or No answer, and there's good hope for the strong one as well.Aug 16, 2012
- There is an implicit limitation that some may find disappointing. The algorithm M only works for
*computable*problems with*computable*proofs. These are countably infinite, but the number of*non-computable*problems is not countable and vastly larger. (Actually, there are non-computable problems that are considered "Well-Defined", so the title of the paper is slightly incorrect.) Non-computable programs are hard to describe and reason about, and there are naturally difficulties in using a computer to explore them.Aug 16, 2012