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

111–120 of 311 posts

Re: Turing Oversold?

#111

Post by mushishi »

yann2 wrote: post #24
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…

No one worked in isolation in the past either. Move Newton, Faraday, Maxwell and Einstein 10kms away from where they were born, surround them by a different set of chimps and the story doesnt end the same way. A good book from Niall Ferguson - the Sqaure and the Tower - makes the case tradionally Historians have studied individuals instead of groups because its easier to collect data on one chimp versus the entire tr…

Yup, the influences on e.g. Newton happening to delve into reading up on Archimedes, Descartes, Fermat, and then synthesizing their inventions in his mind with lot of time on his hand, or for that matter Leibniz getting math tutoring from Christiaan Huygens seem to be crucial in relation to the invention of fluxions/infinitesimals. (Approximately from memory of reading Infinite Powers by Steven Strogatz).

Doesn't diminish their achievement in my mind.

Re: Turing Oversold?

#112

Post by codeflo »

ogogmad wrote: post #100

I need to find a reference for this: Goedel apparently believed that it was impossible to explicitly enumerate all the partial computable functions over the integers, until Turing proved him wrong. He reasoned as follows: - You can't enumerate the total functions because Cantor's diagonal argument is constructive. Given a claimed enumeration of N^N, you can perform Cantor's diagonal construction to produce a computab…

I think the more widespread term for what you call "computably countable" is "computably enumerable", perhaps in part to make the distinction more clear. For example, the set of all natural numbers is (trivially) c.e., but has many non-c.e. subsets. But to understand this is understanding the Entscheidungsproblem, so it shouldn't be surprising that this was less clear before that was resolved.

Re: Turing Oversold?

#113

Post by codeflo »

bjornsing wrote: post #87
eynsham wrote: post #74

Earlier quoted context omitted.

The Turing machine has a tape of unbounded size so can’t be built simpliciter. Moreover although it turns out that that model of computation is very robust and sufficient for all purposes in physics (unless black holes or something allow hypercomputation) Turing does not really definitively show that and in a way that can’t be definitively shown. All we have is a lack of counterexamples (admittedly a very convincing…

> The Turing machine has a tape of unbounded size so can’t be built simpliciter. On the contrary, I think this is one of the advantages of Turing’s model: I can imagine standing there in my garage looking on as my universal Turing machine is running low on tape on the left side, and then simply attaching a new roll of fresh empty tape at the end, holding it as it is fed into the machine. :) It’s simply the least leak…

Exactly this. Unbounded doesn't mean infinite, and people are sometimes confused by the distinction.

Re: Turing Oversold?

#114

Post by ogogmad »

codeflo wrote: post #112
ogogmad wrote: post #100

I need to find a reference for this: Goedel apparently believed that it was impossible to explicitly enumerate all the partial computable functions over the integers, until Turing proved him wrong. He reasoned as follows: - You can't enumerate the total functions because Cantor's diagonal argument is constructive. Given a claimed enumeration of N^N, you can perform Cantor's diagonal construction to produce a computab…

I think the more widespread term for what you call "computably countable" is "computably enumerable", perhaps in part to make the distinction more clear. For example, the set of all natural numbers is (trivially) c.e., but has many non-c.e. subsets. But to understand this is understanding the Entscheidungsproblem, so it shouldn't be surprising that this was less clear before that was resolved.

Computably countable is also a correct term. In line with this approach to computability theory: http://math.andrej.com/asset/data/synthetic-slides.pdf

It shows that the unsolvability of the halting problem follows from:

- The computable uncountability of N^N, which can be proved using an identical argument to the one Cantor used to prove the set-theoretic uncountability of N^N.

- The computable countability of the partial maps from N to N.

If the halting problem were solvable, then the second bullet point would contradict the first. So it's essentially a weird twist on set theory that uses constructive logic.

Re: Turing Oversold?

#115

Post by codeflo »

tsimionescu wrote: post #51
bjornsing wrote: post #18

Having an educational background in physics I find the Turing Machine a much more intuitive model of computation than say lambda calculus. To me this is Turing’s main contribution: linking the abstract world of computation to the physical world, and proving that a very simple physical machine can perform any computation (Turing completeness). That’s no small contribution.

> and proving that a very simple physical machine can perform any computation (Turing completeness) This is a misunderstanding of the Turing machine model. The Turing machine is not designed to be a realistically implementable physical machine, and indeed there are no details in Turing's paper on how such a physical machine could be achieved. Instead, the Turing machine model is designed to be a mechanistic model of…

I'm with you, I also found Turing's argument that his machine model captures all of computation very convincing and pointed that out in another thread.

However, for this argument to work, we need to accept both that all computation is captured by Turing machines, and also that what Turing machines do is in fact computable. In essence, Turing machine realizable machine. Maybe some people are more impressed by one, others more by the other direction of that double implication.

Re: Turing Oversold?

#117

Post by KingOfCoders »

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…

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

Re: Turing Oversold?

#118

Post by breuleux »

netcan wrote: post #108
breuleux wrote: post #98

Earlier quoted context omitted.

Why do we need idols, though? If there was no narrative, no idols, no celebrities, would people be less motivated to do science? Why do we need to lie to ourselves so? > If you're already deeply interested in computer science, of course the detailed narrative recognizing dozens of brilliant early computer scientists is richer. Of course! Personally I'm mostly uninterested in who did what, but maybe that's just me. It…

>>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?

Re: Turing Oversold?

#119

Post by codeflo »

ogogmad wrote: post #114
codeflo wrote: post #112

Earlier quoted context omitted.

I think the more widespread term for what you call "computably countable" is "computably enumerable", perhaps in part to make the distinction more clear. For example, the set of all natural numbers is (trivially) c.e., but has many non-c.e. subsets. But to understand this is understanding the Entscheidungsproblem, so it shouldn't be surprising that this was less clear before that was resolved.

Computably countable is also a correct term. In line with this approach to computability theory: http://math.andrej.com/asset/data/synthetic-slides.pdf It shows that the unsolvability of the halting problem follows from: - The computable uncountability of N^N, which can be proved using an identical argument to the one Cantor used to prove the set-theoretic uncountability of N^N. - The computable countability of the p…

I don't doubt that the term is in use, and I understood what you meant. But it's not listed among seven (!) synonyms for computably enumerable on Wikipedia, and more the point, the slides you linked to also don't contain that term.

However, that's not the point I wanted to make. I wouldn't like calling it computably countable even if everyone else did, simply because it gives the wrong intuition about subsets.

Re: Turing Oversold?

#120

Post by 3pt14159 »

KingOfCoders wrote: post #117
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…

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

Not OP, but I agree with them.

The word computer means multiple things. In one sense it the abstraction of universal computation. Imagine a world where actual physical computers didn't progress to universal computation, but were stuck being purpose built to the present day. The field of computer science would be utterly different because they couldn't actually compute anything with their science. They could just discuss computability in an abstract sense. It'd be like physics without the particle colliders or telescopes or lasers.

I think of the founders of computer science more like the founding fathers of America, rather than a single guy named Turing, but some are more memorable than others.

Post reply on HN