[dnautics]

> I don't understand why Schmidhuber continues to ignore this crucial point.

From TFA:

> There is a seemingly minor difference whose significance emerged only later. Many of Gödel's instruction sequences were series of multiplications of number-coded storage contents by integers. Gödel did not care that the computational complexity of such multiplications tends to increase with storage size. Similarly, Church also ignored the context-dependent spatio-temporal complexity of the basic instructions in his algorithms. Turing and Post, however, adopted a traditional, reductionist, minimalist, binary view of computing. Their machine models permitted only very simple elementary binary instructions with constant complexity, like the early binary machine model of Leibniz (1679)[L79][LA14][HO66] and Zuse's 1936 patent application...

I presume by "seemingly minor" Schmidhuber implies "it turns out to be very important".

[mananaysiempre]

Not to dispute your point, but note the lambda-calculus-as-a-reasonable-machine papers from the last couple of years: it turns out (despite the seeming general understanding to the contrary in the past) that polynomial interpreters for some meanings of “lambda calculus” (including IIRC a weird very general one, call-by-need on open terms) are perfectly possible, meaning that many fundamental questions of computational complexity can be straightforwardly expressed in terms of the lambda-calculus machine as well. Linear-time interpretation (thus e.g. classes L and NL) seemed out of reach last I checked, though.

To echo my other comment here, it’s not that Church himself knew that. Even five years ago people did not know that. It’s not a question of priority. But I find it fascinating and reassuring nevertheless, as actually programming e.g. a self-interpreter for a Turing machine—or for general recursive functions, or for combinatory calculus—is an absolute slog.

[anatoly]

Can you give some links to these recent papers? Sounds interesting. Thanks!

[mananaysiempre]

Didn’t have access to my archive at the time, so got some of the details wrong it seems (e.g. CbV not CbN, result for time is older than I remembered). Main thrust should remain valid, but be careful. In any case, here you go:

Dal Lago, Martini (2008). “The weak lambda calculus as a reasonable machine”. DOI:10.1016/j.tcs.2008.01.044, apparently not on arXiv.

Accattoli (2012). “A fresh look at the lambda-calculus”. DOI: 10.4230/LIPIcs.FSCD.2019.1, apparently not on arXiv.

Accattoli, Dal Lago (2014). “Beta reduction is invariant, indeed”. DOI: 10.1145/2603088.2603105, arXiv: 1405.3311 [cs.LO].

Accattoli, Dal Lago (2016). “(Leftmost-outermost) beta reduction is invariant, indeed”. DOI: 10.2168/LMCS-12(1:4)2016, arXiv: 1601.01233 [cs.PL].

Forster, Kunze, Roth (2020). “The weak call-by-value lambda-calculus is reasonable for both time and space”. DOI: 10.1145/3371095, arXiv: 1902.07515 [cs.CC].

Now that I’m looking through bibliographies, there are apparently other relevant intervening papers in the vicinity, even by some of the same authors, but these are what I’ve looked at personally.

Bonus: the paper

Hackett, Hutton (2019). “Call-by-need is clairvoyant call-by-value”. DOI: 10.1145/3341718, apparently not on arXiv.

is unrelated to questions of complexity but is just so absolutely lovely.

[lostmsu]

It is important for engineering, but as far as I understand it is not that important for math. E.g. Gödel solved the completeness and consistency problems, and Church first solved the decidability.

[jrochkind1]

The OP itself documents:

> Nevertheless, according to Wang,[WA74-96] it was Turing's work (1936) that convinced Gödel of the universality of both his own approach (1931-34) and Church's (1935).

Unless "according to Wang" is meant as "I don't know if I believe it", then apparently it's documented that Godel himself thought Turing's contribution was major and shed important light on the mathematical implications of godel's own work.

There's never any one person that invents anything, it's always built on work that came before.

Reading the OP, I got increasingly bored and tired... ok, what's your point? Yes, clearly Godel and Church especially did foundational work without which Turing's work would not be possible -- and I don't think anyone denies it, anyone with any kind of computer science education is surely familiar with Godel and Church. It's not like they are languishing in obscurity, they are both very well known and respected! Godel especially is widely considered a real giant in his fields. I am as confident that neither Godel nor Church is going to be forgotten for many generations.

But Turing made important contributions that took important steps necessary for the development of CS as a field. It's not a mystery or undeserved why Turing's name ends up remembered.

The OP's point is just that any singular "inventor" is always building on work of may who have come before? OK, sure. Boring. So we should never promote anyone as making important foundational contributions? Well, people aren't gonna stop. Boring.

[chalst]

It's also the case that Church only knew that the notion of function defined by the lambda calculus was coherent once the Church-Rosser property was proven, and that was not published before Turing submitted his article.