A. A. Muchnik [Albert Abramovich] / Альберт Абрамович Мучник

(2 Jan. 1934 - 14 Feb. 2019)

A. A. Muchnik: `Solution of Post's reduction problem and of certain other problems in the theory of algorithms', Received: 19 Feb. 1957.

"I do not know if you have heard that `Post's problem', whether there are degrees of unsolvability among problems of the form (\exists y) \phi (y,x), where \phi 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)."

-- Letter from K. Gödel to J. von Neumann, 20 Mar. 1956 (discovered in the Nachlass of von Neumann, 1988; no reply is known to exist, and von Neumann died on 8 Feb. 1957).

Richard M. Friedberg: `Two recursively enumerable sets of incomparable degrees of unsolvability (solution of Post's problem, 1944)', communicated by K. Gödel, 11 Dec. 1956, Proceedings of the National Academy of Sciences of the USA.

N. B.: Richard M. Friedberg [Michael] (b. 8 Oct. 1935) is a student of T.-D. Lee and Professor Emeritus of Physics at Barnard College and at Columbia University (1968-2003). He is the author of `An Adventurer's guide to Number theory', 1968. His father, Charles K. Friedberg [Kaye] (14 Sep. 1905 - 14 Jul.1972), was the author of `Diseases of the Heart', W. B. Saunders, 1949, 1956, 1966. The books of both father and son are with me.