/Tech6h ago

CMU's Aran Nayebi argues Kurt Gödel's 1934 lectures lacked computational universality, drawing a rebuttal from Jürgen Schmidhuber

Nayebi says Gödel defined only halting total recursive functions.

4003347

#86

Original post

Aran Nayebi@aran_nayebi#1431inTech

@SchmidhuberAI Gödel 1934 still misses out on universality since those are total recursive functions (always halting), but you need partial recursive functions in the Church-Turing sense if you want a universal evaluator, as it may not always halt.

Jürgen Schmidhuber@SchmidhuberAI

Ok: Gödel 1931---> Gödel 1931-1934 [GOD34], as mentioned in the report.

[GOD34] K. Gödel (1934). On undecidable propositions of formal mathematical systems. Notes by S. C. Kleene and J. B. Rosser on lectures at the Institute for Advanced Study, Princeton, New Jersey, 1934, 30 pp. (Reprinted in M. Davis, (ed.), The Undecidable. Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions, Raven Press, Hewlett, New York, 1965.)

5:04 AM · Jun 25, 2026 · 93 Views

Sentiment

Sentiment building, check back later.

Cluster Engagement

Digg Deeper

No Digg Deeper questions have been answered for this story yet.

Posts from X

Most Activity

Jürgen Schmidhuber@SchmidhuberAI

@aran_nayebi But given some axiomatic system, Gödel essentially had nonhalting programs that never stopped because they searched for unprovable theorems.

Aran Nayebi@aran_nayebi

4h9800

BOOKMARKS1

Aran Nayebi@aran_nayebi

@SchmidhuberAI Right, but that universality is coming from open-ended proof search over encoded programs, not from Gödel 1931's primitive recursion or Gödel 1934's total recursive functions themselves.

Jürgen Schmidhuber@SchmidhuberAI

@aran_nayebi Sure, but you can express any program in an axiomatic system, and the proof search will deduce its consequences (simulate its behavior).

1h2001

REPLIES1

Jürgen Schmidhuber@SchmidhuberAI

@aran_nayebi Sure, but you can express any program in an axiomatic system, and the proof search will deduce its consequences (simulate its behavior).

Aran Nayebi@aran_nayebi

A process can fail to halt without being universal. For example, "search forever for a proof of this unprovable sentence" is a partial procedure, but it is only one very specific semidecision process. A universal evaluator is much stronger: it takes an arbitrary program code e and input x, then simulates that program's behavior.

3h8900

Aran Nayebi@aran_nayebi

Jürgen Schmidhuber@SchmidhuberAI

@aran_nayebi But given some axiomatic system, Gödel essentially had nonhalting programs that never stopped because they searched for unprovable theorems.

3h6201