[FOM] Harvey Friedman's "hyperaliens"
Martin Davis
martin at eipye.com
Sat Mar 13 12:53:33 EST 2004
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
More information about the FOM
mailing list