News for hackers. Stuff that matters.
Re:Turing machines that should run forever by dzdt on Wednesday May 11, 2016 @01:57PM (#11677609)
A Turing machine is just a computer program.

The Goldbach Conjecture example is just a program to loop through and test that each successive even integer can be reached as the sum of two prime numbers. If there is a counterexample to the conjecture, then theoretically this program will eventually find it. For these purposes, the authors don't care if the program calculates efficiently, but are interested in the length of the program. So brute force is fine.

The Riemann Hypothesis and ZFC programs similarly are just brute force searching for counterexamples.

The existence of programs to search for counterexamples is not new or surprising. I am not so sure what part of this work is new. I guess it is the discussion of philisophical implications.

Re:Turing machines that should run forever by sp332 on Wednesday May 11, 2016 @02:01PM (#11677651)
What's new here is putting a specific upper bound on the complexity of the problem. A Turing machine using only binary symbols and at most 7,918 states is enough to prove or disprove ZFC.
Re:Turing machines that should run forever by chriswarbo on Wednesday May 11, 2016 @02:20PM (#11677823)
To me, the use of Turing machines seems a little gimmicky; they're very far removed from the way we actually program, or reason about programs. The difficult problem here seems to be compilation: going from a usable program definition, either formal or informal, down to the bizarre world of Turing machines, either by hand or automatically.

To me, binary combinatory logic and binary lambda calculus seem like much more sensible languages for performing these kinds of algorithmic information theory experiments.

Re:Turing machines that should run forever by tromp on Wednesday May 11, 2016 @02:53PM (#11678121)
Scott commented on the Turing Machine vs lambda calculus approaches in:

http://www.scottaaronson.com/blog/?p=2725#comment-1085117

showing a clear preference for the "physical" operation of Turing Machines.

In the end, complexities are not that far apart, considering that

https://gist.github.com/anonymous/a64213f391339236c2fe31f874...

describes a 27 state Goldbach checking TM, which takes no more than 378 bits to encode, while

https://github.com/tromp/AIT/blob/master/goldbach.lam

describes an equivalent 267 bit Lambda Calculus term, which can also be represented as this

https://github.com/tromp/AIT/blob/master/goldbach.gif

lambda diagram, as explained in

http://tromp.github.io/cl/diagrams.html

Re:Turing machines that should run forever by sp332 on Wednesday May 11, 2016 @02:30PM (#11677898)
The proof was actually written in Laconic, and then compiled down to a TM. We already know certain things about TMs (like busy beaver and the halting problem) so you don't have to re-prove those things about your new machine if you can just prove that it's equivalent to a TM. It's mainly used as a convenient way to keep score. If some other proof can be proven equivalent to a TM with fewer states, then you have a better upper bound.