[FOM] Harvey Friedman's "hyperaliens"

[Martin Davis]

First, the obvious remark that none of the conceptual problems haunting the 
proponents of hypercomputation stand in the way of Harvey's idea because of 
the bound he places on the size of the Turing machines. But there are 
problems of other kinds.

I believe I could produce a Turing machine within Harvey's bounds of 100 or 
so quadruples that will halt (starting on an empty tape) if and only if the 
Goldbach conjecture is false. Suppose we put this TM into the aliens' magic 
device and the output reads: doesn't halt. Have we proved the Goldbach 
conjecture to anyone's satisfaction? Of course, if the aliens relent and 
explain how their machine works, it would be another matter.

I'm reminded of Post's struggle with his problem of tag in the 1920s 
(proved unsolvable 40 years later by Marvin Minsky). Post had reduced the 
decision problem for systems like Principia Mathematica to that of very 
simple looking combinatorial systems he called "normal". As a first step in 
attacking that problem, he came to "tag" as a simplified form. Working on 
special cases of tag (some of which remain open to this day) he became 
increasingly frustrated because he kept running into problems in number 
theory, whereas, as he said later, he had hoped that number theory itself 
(as formalized in PM) would be dissolved into these "easy" combinatorial 
problems.

Martin