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

291–300 of 311 posts

Re: Turing Oversold?

#291

Post by nl »

generalizations wrote: post #213
jimhefferon wrote: post #187

Earlier quoted context omitted.

> Is it possible Yes, the set of functions computable with mu recursion, or with lambda calculus, is the same as the set of functions computable with a Turing machine. (Turing in his original paper showed that the set is the same for his system and Church's, and the proofs for mu recursion and many other systems are well-known.) > I'll totally agree that from a teacher's perspective, the Turing machine is the better…

Thanks, I think I understand now. I thought there was a distinction between the mathematical idea of what computation is, and the engineering we've invented to implement that computation, and so I didn't really get the significance/literalness of what you were saying about mechanization. It does seem weird to me though that we're letting our engineering limitations determine how we think about these things mathematic…

It's not as simple as engineering limitations determining how we think.

Turing machines do have mathematical advantages in some areas. See this siblings comment: https://news.ycombinator.com/item?id=28541800

Re: Turing Oversold?

#292

Post by agumonkey »

pvg wrote: post #16
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…

even Einstein also stood in the shoulders of giants People have had that perched-on-giants feeling for some time: This concept has been traced to the 12th century, attributed to Bernard of Chartres. Its most familiar expression in English is by Isaac Newton in 1675: "If I have seen further it is by standing on the shoulders of Giants." https://en.wikipedia.org/wiki/Standing_on_the_shoulders_of_g...

Note that this might be a double meaning jab at hook. Sadly brilliant if true

Re: Turing Oversold?

#293

Post by jecel »

cybernautique wrote: post #285
jecel wrote: post #279

Earlier quoted context omitted.

I always mention the Rekursiv in my talk about Smalltalk computers. Its problem was being a CISC in the era of RISC. The Manchester Mushroom from just a little later had initially the same problem but went through a major redesign when they saw the JIT compilers for Self on the Sun Sparc processor.

I'd never heard of the Mushroom! Thank you for making me aware of it! A quick DDG search returned no results; I'd appreciate any links you have on the topic! I'd also love to see your talk! Do you think a RISC Rekursiv could be achieved? What value, if any, do you think such might have in our current world?

This is the current Mushroom page:

http://www.wolczko.com/mushroom/

The slides for my 2019 talk about Smalltalk computers (in LibreOffice and PDF formats):

http://www.merlintec.com/download/2019_slides_jecel_fast1v2....

http://www.merlintec.com/download/2019_slides_jecel_fast1v2....

and the video (1 hour and 13 minutes):

https://www.youtube.com/watch?v=tATpzsyC6OA

If you replace the Rekursiv's special microcode memory with a cache to allow microcode to live in main memory you will essentially have a RISC version of the machine. I have adopted this solution in several of my own designs.

Re: Turing Oversold?

#294

Post by jhgb »

teruakohatu wrote: post #278
jhgb wrote: post #269

Earlier quoted context omitted.

Not sure what improvement Pearse made over, say, Ader.

Pearse archived semi-controlled flight 300 cm above the ground verses Ader's uncontrolled ground effect flight 20cm above the ground.

I have no idea what is "a semi-controlled flight". Is it like "semi-riding a bike"?

Re: Turing Oversold?

#295

Post by tialaramex »

SquishyPanda23 wrote: post #277
tialaramex wrote: post #270

Earlier quoted context omitted.

A whole bunch of Computer Science is only relevant for actual computers not Turing Machines. When I was (a student) at University they didn't teach Wait-Free versus Lock-Free concurrent algorithms, but that's an important 21st century topic because actual computers today are capable of many simultaneous operations, and it's totally possible to write a program that isn't even Lock-free and may literally make no progre…

Yes that is true. There are applied sub-disciplines for all of the science. Typically you would call that something like "applied computer science" or "computer engineering", but CS is new enough that it hasn't split like that yet. Nobody is saying that's not important. But the field as a whole began before mechanical computers were invented or practical, and there are several subfields that are basically indistingui…

I mean, my university still has separate Chemistry and Astronomy departments, but at yours following your preferred nomenclature, how do they distinguish among all the resulting departments called stuff like "Applied Philosophy", "Applied Philosophy" and "Applied Philosophy" ? Or is it that for some reason you think only Computer Science should be singled out in this way?

Re: Turing Oversold?

#296

Post by Ar-Curunir »

SquishyPanda23 wrote: post #277
tialaramex wrote: post #270

Earlier quoted context omitted.

A whole bunch of Computer Science is only relevant for actual computers not Turing Machines. When I was (a student) at University they didn't teach Wait-Free versus Lock-Free concurrent algorithms, but that's an important 21st century topic because actual computers today are capable of many simultaneous operations, and it's totally possible to write a program that isn't even Lock-free and may literally make no progre…

Yes that is true. There are applied sub-disciplines for all of the science. Typically you would call that something like "applied computer science" or "computer engineering", but CS is new enough that it hasn't split like that yet. Nobody is saying that's not important. But the field as a whole began before mechanical computers were invented or practical, and there are several subfields that are basically indistingui…

I mean, if you want to relegate CS to only mean theoretical CS, then you’d be in a small population: most theorists don’t want that, even. One of the cool things about CS is the rich interplay between applications and theory, and separating the two would only harm both.

Re: Turing Oversold?

#297

Post by Ar-Curunir »

SquishyPanda23 wrote: post #240
Ar-Curunir wrote: post #190

Earlier quoted context omitted.

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

Sure, if you take "computer" to mean "something that computes". In that case it would include humans. There was a great deal of research into things that can be effectively computed that goes back even before the focus of this article. And of course "computer" used to refer to humans who computed before the invention of mechanical computers. But it's certainly not the study of what mechanical computers can do. Among…

Mechanical computers approximate Turing Machines, just like NP approximates RE: instead of asking “does this program halt?”, we ask “does this program halt in N steps?”.

If N is sufficiently (polynomially) large, the two are approximately equal.

Re: Turing Oversold?

#298

Post by Karrot_Kream »

cybernautique wrote: post #253
Karrot_Kream wrote: post #245

Earlier quoted context omitted.

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…

Your comment made me think a lot! Thanks for that. If I had to "capture" what made analysis interesting for me, it's not just the notion of continuity, but the idea that we're analyzing the behavior of an object in the concrete instead of the abstract. That means taking an object and deriving all sorts of behaviors, instead of building up algebras from simple group/ring operations. To bring this back into PLT, it would probably mean the ability to place computational complexity bounds on functions/methods. Something like Mercury's Execution Modes https://www.mercurylang.org/information/doc-latest/mercury_r...

Re: Turing Oversold?

#299

Post by bo1024 »

AnimalMuppet wrote: post #260
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?

I'd say no, not on its own. It's not clear how to implement a Lisp program in hardware. You need some steps which today involve a von Neumann architecture and an imperative assembly language that implement Lisp constructs...

Re: Turing Oversold?

#300

Post by chalst »

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…

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.
Post reply on HN