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.
[ Parent
| on HN ]
There are no comments on this comment yet.