[FOM] Freeman Dyson on Inexhaustibility

[Karlis Podnieks]

According to some computer scientists, Godel's Incompleteness Theorem is a
"simple corollary" of a more fundamental phenomenon - the existence of
recursively enumerable non-recursive sets (or, unsolvability of the halting
problem for Turing machines).

In principle, any non-recursive predicate xP(x) could serve as an
inexhaustible source of PhD theses: your first doctoral student may work on
P(0), the second one - on P(1), etc. ad infinitum.

This aphorism is due to a computer scientist working in Novosibirsk (Russia)
in 1970s.

Best wishes,
Karlis.Podnieks at mii.lu.lv
www.ltn.lv/~podnieks
Institute of Mathematics and Computer Science
University of Latvia

----- Original Message ----- 
From: "charles silver" <silver_1 at mindspring.com>
To: <fom at cs.nyu.edu>
Sent: Tuesday, April 27, 2004 3:45 PM
Subject: [FOM] Freeman Dyson on Inexhaustibility