f*********g
发帖数: 632 | 1 Princeton, 20 March 1956
Dear Mr. von Neumann:
GÄodel Book|Wigderson - rev. 2010-0708 5
With the greatest sorrow I have learned of your illness.
The news came to me as quite unexpected. Morgenstern
already last summer told me of a bout of weakness you once
had, but at that time he thought that this was not of any
greater significance. As I hear, in the last months you
have undergone a radical treatment and I am happy that this
treatment was successful as desired, and that you are now
doing better. I hope and wish for you that your condition
will soon improve even more and that the newest medical
discoveries, if possible, will lead to a complete recovery.
Since you now, as I hear, are feeling stronger, I would like
to allow myself to write you about a mathematical problem,
of which your opinion would very much interest me: One can
obviously easily construct a Turing machine, which for every
formula F in first order predicate logic and every natural
number n, allows one to decide if there is a proof of F of
length n (length = number of symbols). Let Ã(F; n) be the
number of steps the machine requires for this and let
Á(n) = maxF Ã(F; n). The question is how fast Á(n)
grows for
an optimal machine. One can show that Á(n) ¸ k ¢ n. If
there
really were a machine with Á(n) ¼ k ¢ n (or even Á
(n) ¼ k ¢ n2),
this would have consequences of the greatest importance.
Namely, it would obviously mean that in spite of the
undecidability of the Entscheidungsproblem, the mental work
of a mathematician concerning Yes-or-No questions (apart
from the postulation of axioms) could be completely replaced
by a machine. After all, one would simply have to choose
the natural number n so large that when the machine does not
deliver a result, it makes no sense to think more about the
problem. Now it seems to me, however, to be completely
within the realm of possibility that Á(n) grows that slowly.
Since 1.) it seems that Á(n) ¸ k ¢ n is the only
estimation
which one can obtain by a generalization of the proof of the
undecidability of the Entscheidungsproblem and 2.) after
all Á(n) ¼ k ¢ n (or Á(n) ¼ k ¢ n2)
only means that the number of
steps as opposed to trial and error can be reduced from N
to logN (or (logN)2). However, such strong reductions
appear in other finite problems, for example in the
computation of the quadratic residue symbol using repeated
application of the law of reciprocity. It would be
interesting to know, for instance, the situation concerning
the determination of primality of a number and how strongly
in general the number of steps in finite combinatorial
problems can be reduced with respect to simple exhaustive
search.
I do not know if you have heard that "Post's problem,"
whether there are degrees of unsolvability among problems of
the form (9y)Á(y; x), where Á is recursive, has been solved in
the positive sense by a very young man by the name of
Richard Friedberg. The solution is very elegant.
Unfortunately, Friedberg does not intend to study
mathematics, but rather medicine (apparently under the
influence of his father). By the way, what do you think of
the attempts to build the foundations of analysis on
ramified type theory, which have recently gained momentum?
You are probably aware that Paul Lorenzen has pushed ahead
with this approach to the theory of Lebesgue measure.
However, I believe that in important parts of analysis
non-eliminable impredicative proof methods do appear.
I would be very happy to hear something from you personally.
Please let me know if there is something that I can do for
you. With my best greetings and wishes, as well to your
wife,
Sincerely yours,
Kurt GÄodel
P.S. I heartily congratulate you on the award that the American
government has given to you. | f*********g
发帖数: 632 | 2 只有点击看的，没有回帖的，真郁闷啊。
难道大家都没兴趣说两句？
【在 f*********g 的大作中提到】
: Princeton, 20 March 1956
: Dear Mr. von Neumann:
: GÄodel Book|Wigderson - rev. 2010-0708 5
: With the greatest sorrow I have learned of your illness.
: The news came to me as quite unexpected. Morgenstern
: already last summer told me of a bout of weakness you once
: had, but at that time he thought that this was not of any
: greater significance. As I hear, in the last months you
: have undergone a radical treatment and I am happy that this
: treatment was successful as desired, and that you are now
| l******e
发帖数: 470 | 3 您来将2句儿把
【在 f*********g 的大作中提到】
: 只有点击看的，没有回帖的，真郁闷啊。
: 难道大家都没兴趣说两句？
|
|
