Turing Oversold? • Hacker News Board

Re: Turing Oversold?

#191

Post by WorldMaker » Wed, Sep 15, 2021, 4:40 PM UTC

generalizations wrote: post #172

jimhefferon wrote: post #144

Earlier quoted context omitted.

The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.) Church had piles of stuff that he and his students produced that were computable with the lambda calc…

I'm still a little confused. It seems like Turing came up with something that works, and clearly fulfills precisely what Godel and Church and Turing were all looking for; but it also seems like it's a mathematically inelegant solution. Is it possible that in the future we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'? If so, it se…

That's the central argument in the Church-Turing Theory isn't it? Church felt very strongly that the difference between his and his students' "elegance" and Turing's "practical" was a difference only in abstraction and that the two models were equivalent and translatable (you can write in one abstraction and convert it to the other).

That theory continues to bear fruit as the history of programming languages is almost entirely about bringing new and "better" abstractions to problems and then translating them to "dumber, more practical" machines. We have programming languages today modeled directly off the elegance of (though now sometimes still a few steps removed from being direct implementations of) the lambda calculus and mu-recursive functions, and the amazing thing is that they work great even given how "dumb" and "inelegant" our machines can be in practice.

Re: Turing Oversold?

#192

Post by bentonite » Wed, Sep 15, 2021, 4:46 PM UTC

breuleux wrote: post #118

netcan wrote: post #108

Earlier quoted context omitted.

>>They're not the markers of exceptional genius we want to think they are, not for Turing or Einstein, but not for anyone at all, really. The point isn't to prove that they're special. The point is that something special happened and these people are designated symbols for that... and they're kind of selected for being good at this. We're not doing this for them, they're dead. The celebrity of Einstein is a deificati…

But what purpose do these idols or symbols serve, exactly? I'm speaking as someone who doesn't care who came up with relativity and doesn't care whether there is a founding person of computer science or not let alone who that would be, and would like to know what others see. Is it an inspiration thing? A motivation thing?

I'd say its a bit of both inspiration and motivation. That said, I think the main motivators for these kinds of idols/heroes are to craft ethical or normative stories for how people should (or shouldn't) behave as well as to assist with teaching people theories and concepts.

Learning about why correlation doesn't equal causation (and spurrious correlations) is more impactful if you also learn about Wakefield's sins at the same time. He's a villian.

Archimedes and the bathtub is a great story - and I learned it in elementary school and still remember it and the lessons it teaches. We like to associate people with events and they help for learning and retaining information.

Re: Turing Oversold?

#193

Post by dnautics » Wed, Sep 15, 2021, 4:56 PM UTC

bo1024 wrote: post #101

We've been over this. Gödel's mu-recursive functions were a poor model of computation because it's completely unclear how to physically implement the arbitrary-function minimization operator. So people didn't see how to build a machine that calculates this way. Similarly, there's no clear way how to mechanize lambda calculus. Turing Machines, on the other hand, were instantly obviously mechanizable. It was clear that…

> 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".

Re: Turing Oversold?

#194

Post by acchow » Wed, Sep 15, 2021, 4:58 PM UTC

generalizations wrote: post #172

jimhefferon wrote: post #144

Earlier quoted context omitted.

The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.) Church had piles of stuff that he and his students produced that were computable with the lambda calc…

I'm still a little confused. It seems like Turing came up with something that works, and clearly fulfills precisely what Godel and Church and Turing were all looking for; but it also seems like it's a mathematically inelegant solution. Is it possible that in the future we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'? If so, it se…

> Is it possible that in the future we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'?

Re: Turing Oversold?

#195

Post by dnautics » Wed, Sep 15, 2021, 5:01 PM UTC

Ar-Curunir wrote: post #190

SquishyPanda23 wrote: post #173

Earlier quoted context omitted.

> Turing Machines, on the other hand, were instantly obviously mechanizable. It was clear that one could build a physical machine to run any Turing program without human input. Harold Abelson points out in one of his lectures [0] that computer science isn't about computers any more than biology is about microscopes. From that perspective, it is clear that Turing found an existing discipline of computer science and ma…

Computer Science is about what computers can do. To decide the latter, you have to first decide what a computer is. Turing Machines were the first abstractions that intuitively captured what it means to compute something

that's not the case, according to the article. If anything the article implies the opposite. Turing machines were a re-abstraction of Godel's computational model that provided a path to mechanical realization.

Also if you ever work with the turing machine (NFA hooked up to an infinite recording tape) it is not at all "intuitive" that this construction comprehensively captures the world of computation.

Re: Turing Oversold?

#196

Post by earleybird » Wed, Sep 15, 2021, 5:13 PM UTC

jimhefferon wrote: post #144

KingOfCoders wrote: post #117

Earlier quoted context omitted.

"For example, it was claimed that Turing founded computer science.[...] Turing's 1936 paper provided the "theoretical backbone" for all computers to come." So your argument is, because it is unclear how to "physically implement the arbitrary-function minimization operator", Turing is the better "theoretical backbone" and has founded computer science?

The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.) Church had piles of stuff that he and his students produced that were computable with the lambda calc…

In a nutshell, Church asserted effective computability by saying "look what you can do with the lambda calculus". Turing took the philosophical approach saying "this is what it means to compute". To Godel, Church's argument was incomplete. Turing provided the direct argument. Godel was convinced.

Re: Turing Oversold?

#197

Post by 6gvONxR4sf7o » Wed, Sep 15, 2021, 5:17 PM UTC

bodge5000 wrote: post #182

IshKebab wrote: post #109

Earlier quoted context omitted.

> of wanting to be the center of attention It seemed more like he felt he was unfairly being uncredited. Which is probably why he wrote this - he now cares deeply about giving credit to the right people.

Surely the more noble cause for that would be giving more credit to others, rather than attempting to take away credit from a well known figure. This article is somewhat about the other important figures who's knowledge Turing's was built off, but its central point is that Turing gets too much credit. I understand why he'd care about that if he'd been uncredited and watched peers be overcredited, but I'd hardly call…

The article is full of credit given to a huge number of people.

Re: Turing Oversold?

#198

Post by dwohnitmok » Wed, Sep 15, 2021, 5:18 PM UTC

generalizations wrote: post #172

jimhefferon wrote: post #144

Earlier quoted context omitted.

The question in the air in 36-ish was something like, "OK, clearly we can mechanically compute things like the sum of two numbers or the prime factorization of a number. But are there other things that can be computed with a discrete and deterministic mechanism?" (At the time they called these "effective" functions.) Church had piles of stuff that he and his students produced that were computable with the lambda calc…

I'm still a little confused. It seems like Turing came up with something that works, and clearly fulfills precisely what Godel and Church and Turing were all looking for; but it also seems like it's a mathematically inelegant solution. Is it possible that in the future we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'? If so, it se…

> we'll find a way to show that Gödel's mu-recursive functions or Church's lambda calculus also precisely describe 'what a machine can do'?

This is already proven to be the case. Mu-recursion (which IIRC is not Godel's general recursive functions, despite what Wikipedia says; Kleene was the originator of the mu operator. Godel's general recursive functions are defined in a separate, but yet again equivalent way that directly extends primitive recursion), Turing machines, and the lambda calculus are all proven to be exactly equivalent to each other. The fact that these three independent approaches to computability are all equivalent is why we have strong informal justification that the Church-Turing Thesis (a non-mathematical statement) holds.

Separately, there's a sentiment that I've seen come up several times on HN that somehow the lambda calculus, mu-recursion, or general recursion is more "mathematical" and Turing machines are less "mathematical."

I want to push back on that. The mathematical field of computability is based almost entirely off of Turing machines because there are many classes of mathematical and logical problems that are easy to state with Turing machines and extremely awkward/almost impossible to state with the lambda calculus and mu-recursion (this is consistent with my previous statement that the three are all equivalent in power because computability theory often deals with non-computable functions, in particular trying to specify exactly how non-computable something is). The notion of oracles, which then leads to a rich theory of things like Turing jumps and the arithmetical hierarchy, is trivial to state with Turing machines and very unwieldy to state in these other formalisms.

Likewise the lambda calculus and mu-recursion (but not general recursion) provide a very poor foundation to do complexity theory in CS. Unlike Turing machines, where it is fairly easy to discern what is a constant time operator, the story is much more complicated for the lambda calculus, where to the best of my knowledge, analyzing complexity in the formalism of the lambda calculus, instead of translating it to Turing machines, is still an open problem.

There is indeed a mathematical elegance to Turing machines that makes it so that most of the mathematics of computability is studied with Turing machines rather than the lambda calculus.

The lambda calculus on the other hand is invaluable when studying programming language theory, but we should not mistake PLT to be representative of the wider field of mathematics or theoretical CS.

EDIT: I should perhaps make clear that if I put on my mathematical hat, mu-recursive functions seem like the most familiar formalism, because they align with a common way families of things are defined in mathematics (specify individual members and then generate the rest through some relationship). However, I would contend that for the majority of mathematicians outside of computability theory, the lambda calculus and Turing machines seem equally "strange."

Re: Turing Oversold?

#199

Post by 6gvONxR4sf7o » Wed, Sep 15, 2021, 5:29 PM UTC

bodge5000 wrote: post #176

The problem with technically correct allocation of of credit is that to be truly technically correct, it gets very messy very quickly, as all knowledge is built on other knowledge. The credit for founding computer science would be "[absolutely massive list of people] and finally of course, the one we call Ung, who discovered the wheel". That might seem pedantic and it is, but you need to define exactly where the line…

Those aren’t the only options. We can give credit without creating mythic heros. Giving technically correct precise allocation of credit is messy, you’re right. But so is defining what ‘tall’ means, so the precision is beside the point. You don’t need to define exactly where the line is drawn.

It reminds me of voting systems, but maybe that’s just because of the election yesterday. If you want to give singular nontransferrable credit, the things you say are important because giving someone credit takes it away from someone else. Division and fighting become the right answers. But if you spread the credit around, saying Leibniz and Newton both get calculus credit (and probably not just those two!), then discussions of which one should get the title of The One And Only Calculus Hero just seems absurd.

Re: Turing Oversold?

#200

Post by colechristensen » Wed, Sep 15, 2021, 5:32 PM UTC

pantulis wrote: post #4

There are a lot of true facts thrown in the article, but it does not explore the reason why this is. I feel the era of great thinkers who single handledly performed disruptive breakthroughs in their field, the Galileos and Newtons, was over with the Einstein-era (and even Einstein also stood in the shoulders of giants). No one works in isolation any more, and that is not a bad thing. You can subject any relevant figu…

Nobody exists in a vacuum, but I think Kuhn was right: scientific progress is made up of long periods of incremental work split between short bursts of paradigm shifts. Those shifts are more likely to rest on a few very influential people who take the current state and look at it in a considerably different way. We haven’t had that in physics in quite a long time and might not again.