Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Turing Oversold?

people.idsia.ch

Post reply on HN
Print view View original

251–260 of 311 posts

Re: Turing Oversold?

#251

Post by [deleted] »

hardlianotion wrote: post #246
Dylan16807 wrote: post #233

Earlier quoted context omitted.

In a theoretical sense, an unbounded number is always finite. In a practical sense, turing machines don't voraciously consume tape. Adding extra feet of tape gives you an exponential increase in what you can compute. So if you set up a program to be reasonably judicious with its tape use, you can just say that if it reaches an end you pause it for a day, head to the shop, and buy another reel. Big computations take a…

Any given number is always bounded. I am not sure it makes sense to talk about an unbounded number

[deleted]

Re: Turing Oversold?

#252

Post by mananaysiempre »

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…

And Schönfinkel’s combinatory logic ten years earlier (we are talking priority here, right?) was even more awkward.

There’s also the point (mentioned e.g. by Wadler in his “Propositions as types” talk) that Gödel didn’t actually realize how pervasive universal computation was and actively pushed back against Turing proclaining the equivalence. This is not to accuse him—he wasn’t particularly obstinate or unfair about it and, furthermore, came to understand the idea fairly quickly. But it’s not at all uncommon in science for the one who actually invented a thing to fail to realize what it was that they just invented, and somebody else comes years or in some unfortunate cases decades later and announces the founding of a new area of knowledge on that already-discovered site. Whom the later naming will associate with the discovery is a toss-up, but it’s generally fair and in good taste, I think, to mention both.

Re: Turing Oversold?

#253

Post by cybernautique »

Karrot_Kream wrote: post #245
cybernautique wrote: post #234

Earlier quoted context omitted.

For me, personally, I really like the lambda calculus as a tool to organize and better my computational thinking. I came into programming/computer science from a mathematics degree; I read some old treatises on recursion theory[1] and fell in love. I couldn't ever quite wrap my head around the Turing Machine formalism, but kept at it for a while. Finding Barendregt's paper [2] was a huge shock! I grasped it much quic…

FWIW Nothing wrong with having fun with computing, and implementing lambda calculus on bare-metal can be as fun as any other computational exploration, so good on ya! Thanks for clearing up that it's the formalism you find interesting. Also, to offer a counterpoint, I'm also from a math background, but I was more of an analysis person (as much as one can be in mathematics where it's all related) than an algebra perso…

Nah mate, s'all good! It's great to hear your feedback; I am very much of the algebraist spirit myself (I barely passed my Rudin-based real analysis course). Our experiences definitely align. FP feels much more like my favorite parts of math.

Out of curiosity, can you identify any areas in PLT that could be made more analyst-friendly?

Intuitively, it feels that PLT is almost necessarily of the algebraist; to me, one of the big divides is the discreteness of algebra vs the continuity of analysis. Would it help if there was a PLT that exhibited a greater degree of continuousness? If so, what do you think that might look like?

Re: Turing Oversold?

#254

Post by mananaysiempre »

dnautics wrote: post #193
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 ig…

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.

Re: Turing Oversold?

#255

Post by rg111 »

Also see this: https://news.ycombinator.com/item?id=27536974

It's almost like Schmidhuber hates Turing and wants the world to worship Godel.

It's personal for him.

He also wrote a tweet and maybe another post where he ranked up all countries of Europe and says that Europeans collectively got the most medals in Olympics and hence they are superior.

He suffers from this weird and serious case of European Supremacy.

I know about his actual works (not what he claims to have done).

And based on that I respect him.

He also has got a cult of people following him and who will gang up on any dissenters, i.e. people not thinking of him as a walking god.

Schmidhuber has actual contributions, I know.

Now he moved to a country with extremely bad record of human rights, and has policies and implementation that put the Taliban to shame.

Now he is promoting the institution left and right any opportunity he gets.

He is very hard to take seriously.

Re: Turing Oversold?

#256

Post by rg111 »

chagen wrote: post #217
dilap wrote: post #154

Earlier quoted context omitted.

I really enjoyed Stephen Wolfram's mini-bio of her. https://writings.stephenwolfram.com/2015/12/untangling-the-t... I very much recoginized from that that she had the attitude and experience of a "programmer," so I would say she was the first programmer, in the modern sense.

Ada Lovelace's father was Lord Byron?! TIL

I was surprised to learn that as well.

I learned about it in Walter Isaacson's Innovators.

Re: Turing Oversold?

#257

Post by YeGoblynQueenne »

Labo333 wrote: post #40

I'm not going to comment on the actual content that is mostly [1] scientifically correct, but Schmidhuber (the author) has a record of wanting to be the center of attention [2] (even though LeCun is not better on that matter). Also, a third of the sources are written by him... Just look at his previous blog post [3], in which he explains that the most cited neural networks all cite works by him. These papers cite doz…

>> I'm not going to comment on the actual content that is mostly [1] scientifically correct, but Schmidhuber (the author) has a record of wanting to be the center of attention [2] (even though LeCun is not better on that matter).

You_again wants his work and that of others properly recognised. For example, his article, titled Critique of Paper by "Deep Learning Conspiracy" (Nature 521 p 436) [1] that is referenced by your link to wikipedia, cites a couple dozen pioneers of deep learning, quite apart from Schmidhuber hismelf. Quoting from it:

>> 2. LBH discuss the importance and problems of gradient descent-based learning through backpropagation (BP), and cite their own papers on BP, plus a few others, but fail to mention BP's inventors. BP's continuous form was derived in the early 1960s (Bryson, 1961; Kelley, 1960; Bryson and Ho, 1969). Dreyfus (1962) published the elegant derivation of BP based on the chain rule only. BP's modern efficient version for discrete sparse networks (including FORTRAN code) was published by Linnainmaa (1970). Dreyfus (1973) used BP to change weights of controllers in proportion to such gradients. By 1980, automatic differentiation could derive BP for any differentiable graph (Speelpenning, 1980). Werbos (1982) published the first application of BP to NNs, extending thoughts in his 1974 thesis (cited by LBH), which did not have Linnainmaa's (1970) modern, efficient form of BP. BP for NNs on computers 10,000 times faster per Dollar than those of the 1960s can yield useful internal representations, as shown by Rumelhart et al. (1986), who also did not cite BP's inventors.

That is not "wanting to be the center of attention". It is very much asking for proper attribution of research results. Failing to do so is a scientific scandal, especially when the work cited has contributed towards a Turing award.

__________

[1] https://people.idsia.ch/~juergen/deep-learning-conspiracy.ht...

Re: Turing Oversold?

#258

Post by exporectomy »

He seems a bit self-contradictory saying both "value those who ensure that science is self-correcting." and "when it comes to credit assignment in science, the important question is: Who did it first?"

Probably worth stepping back and asking why we have heroes in the first place. It obviously doesn't serve the hero himself because he's dead. It's for the benefit of other people. Perhaps if it seems unfair, people won't be so inspired by them, but that's more about perception and modern culture than reality.

We already have a million and one scientists trying to be the first to discover a novel phenomenon but in a useless and non-self-correcting way and not even bothering to follow up on their own "discovery", perhaps hoping someone else will do the hard work while they enjoy the credit of being first. I'd also say that perhaps it doesn't count if you do it first but your results remain hidden and unused. I'll bet some native African discovered Angel Falls before Angel did, but that knowledge didn't get out to the wider world so what was the point of it?

Re: Turing Oversold?

#259

Post by anatoly »

mananaysiempre wrote: post #254
dnautics wrote: post #193

Earlier quoted context omitted.

> 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 ig…

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 computationa…

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

Re: Turing Oversold?

#260

Post by AnimalMuppet »

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…

> Similarly, there's no clear way how to mechanize lambda calculus.

Is Lisp such a mechanization?

Post reply on HN