News for hackers. Stuff that matters.
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.