3 ms·

unless we're able to simply try all the required Turing machines.

• tialaramex 9y ago
  The tricky bit isn't running the ones that halt and noticing when, but reasoning about all the ones that _don't_ halt in order to convince ourselves that they really never halt. The larger and more complex the machine, the harder it may be for a human to reason about it in this way. For example, suppose it's 1985 and you are examining a machine which seems to be checking all integers X above 204 to see if it can find a^X + b^X = c^X. Does it halt? Unfortunately the only way to answer that question is to wait until 1996 when a proof is published which says Fermat was right, there are no values of X for which this is true. So the machine never halts. [Edited to try to get HN to format the question properly]
  • goialoq 9y ago
    recall this classic: https://blog.regehr.org/archives/140 https://blog.regehr.org/archives/140 C Compilers Disprove Fermat’s Last Theorem