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

51–60 of 311 posts

Re: Turing Oversold?

#51

Post by tsimionescu »

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 what a mathematician does (in rote day-to-day tasks at least). The tape is a representation of the notebook where the mathematician writes down notes. The read head is a representation of the mathematician reading from the notebook.

It's fascinating to read the paper because of this, since it spends quite a few paragraphs showing that this simplification doesn't lose anything of the mathematician's work. It spends some time noting that even though paper is two-dimensional, it can be losslessly compressed on unidimensional tape. It spends time noting that writing/reading one symbol at a time is a good enough approximation for human writing/reading. It spends time noting that the next step doesn't need to depend on more than the current symbol + internal state, as human attention is also focused on a limited number of symbols.

This is actually why Turing's paper is so convincing on the argument of universal computation - not because the machine is realizable, but because it's hard to invent anything that a mathematician does while calculating that is not captured by the Turing machine model.

I very much recommend reading the first part of the paper [0] to see this argument (the second part, where it is proven that this abstract machine can in fact compute all known numbers, is more technical and flew over my own head).

[0] PDF https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Re: Turing Oversold?

#52

Post by endgame »

arethuza wrote: post #44
formerly_proven wrote: post #37

Earlier quoted context omitted.

What I find so strange about The Imitation Game that all of this is pretty well-known; anyone who has skimmed the Wikipedia article of Turing and the overview article on breaking Enigma knows that the movie is pretty much complete horseshit. Most of the alterations in the movie removed things that would have made the movie more interesting instead of the utterly bland story they made up.

I'm struggling to think of any movies that are really historically accurate - the point is to tell a good story to get people to watch it to make a profit. Edit: I'm Scottish so Braveheart is the obvious example - entertaining movie but wildly inaccurate and even manages to get who/what the term "braveheart" refers to wrong.

Master and Commander (the Russell Crowe film)? While it's a fictional story, I've heard it said that it captures the period extremely well.

Re: Turing Oversold?

#53

Post by heurisko »

I watched the "Imitation Game" and read the biography of Turing by Andrew Hodges.

What I found fascinating about the biography was recognising what Turing was describing in theoretical terms, as actual hardware and software concepts today. I know some parts are somewhat obvious, but it was still nice to trace the concepts back to excerpts from his work.

The Imitation Game is a nice fiction, but doesn't portray Turing as having very much agency, in comparison to the real Turing. I think the fictional and real-life characters were completely different.

Re: Turing Oversold?

#54

Post by tsimionescu »

skissane wrote: post #20
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.

> I find the Turing Machine a much more intuitive model of computation than say lambda calculus I think register machines are more intuitive than Turing machines - they are much closer to how real world computers work.

But that's the opposite direction from Turing's intention. The point of the Turing machine model is for the machine to be both mechanically plausible (no magic required) but also equivalent to what a human does when performing computation.

The Turing machine model is a mechanically plausible abstraction of a human performing a computation by following some steps in their mind and with a notebook. The tape stands in for the notebook. The read head stands in for the human's eyes. The write head stands in for their pencil hand. The internal state of the machine stands in for their mental state. At every step, you either read a symbol from the notebook tape and change your mental state in relation to this symbol, or write a symbol based on the current mental state. The procedure itself can be written on the tape, and you can occasionally refer back to it.

The original paper spends a good few pages working out this metaphor and showing that the machine model perfectly abstracts the mathematician's work of computation.

Re: Turing Oversold?

#55

Post by jgrahamc »

heurisko wrote: post #53

I watched the "Imitation Game" and read the biography of Turing by Andrew Hodges. What I found fascinating about the biography was recognising what Turing was describing in theoretical terms, as actual hardware and software concepts today. I know some parts are somewhat obvious, but it was still nice to trace the concepts back to excerpts from his work. The Imitation Game is a nice fiction, but doesn't portray Turing…

The Imitation Game is awful and should never be screened.

Re: Turing Oversold?

#56

Post by OskarS »

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…

> But if you need to choose a Founding Father of Computing Science for the general public, I'd say Alan Turing is the best candidate. Scholars will give due credit to Church, Zuse, von Neumann and all the others.

I agree with this. It's certainly the case that I wish more people knew of Alonso Church and Kurt Gödel, but you have to realize in a "PR" sense that it's simply not going to be feasible to teach the general public about their contributions.

And Turing's contributions were genuinely ground-breaking, there's a reason that computer science is lousy with concepts named after or by him (Turing machines, Turing-completeness, even the word "computing" was arguably coined in "On Computable Numbers"). He also thought deeply and hard about the philosophical implications to computing in a way that others didn't (the "Turing test" being the obvious example).

In addition: when a mathematically inclined person describes any kind of mathematical concept to laymen, the first question is always "Yeah, but what is that actually useful for?", asked with a certain amount of disdain. With Turing, the answer is powerful: "How about defeating the Nazis and laying the foundation for modern society?". That case is harder to make for Church or Gödel: they obviously didn't work for the GCSE, and "lambda calculus" as a concept is a much more abstract thing than Turing machines, which laymen can readily understand (i.e. it's "just" a computer).

Add to that the fact that Turing's story is not just about computing, or code-breaking, it's also the story of the suffering that society inflicted on gay men. The fact that he was shamed into suicide is just all the more reason to celebrate him now.

I agree with the basic point of the article, but I have no issue with giving Alan Turing this title. He earned it.

Re: Turing Oversold?

#57

Post by tsimionescu »

bjornsing wrote: post #25
skissane wrote: post #20

Earlier quoted context omitted.

> I find the Turing Machine a much more intuitive model of computation than say lambda calculus I think register machines are more intuitive than Turing machines - they are much closer to how real world computers work.

Yes, on the abstract computation side of the link register machines are much more intuitive. But on the physical side of the link they are much less intuitive IMHO: it’s much less clear that “this is just a machine that I could build in my garage”.

The Turing machine is definitely not some machine that you could build in your garage. None of the mechanisms are specified or even specifiable. The important part, to Turing ateast, is that it perfectly matches what a human does while computing a number, and that there are no magical steps like 'thinking'. Read symbol, change internal state, write other symbol down, rinse and repeat.

All of the details of how a symbol is read, recognized, how it alters the internal state, how the next symbol is chosen, or even how many symbols you actually need are not mentioned and even considered irrelevant. Turing wasn't building one of these, he was proving that this model captures all known computation, and that even so it is undecidable whether this machine would ever stop for any arbitrary computation.

Re: Turing Oversold?

#58

Post by roenxi »

simonh wrote: post #47
netcan wrote: post #38

Just the references here are probably an amazing resource for early computer science, and I'm not going to argue against such a force. Seems to be a lot of uneasiness, of late, about the way credit is allocated in science. IMO, it's mistaken to point this at the top: nobel laureates, heroic icons like Einstein or Turing. These figures are supposed to be idolized and idealized. Yes, this is "untrue," technically. But,…

Right, we shouldn't underestimate the importance of narratives. We need narratives about the theoretical foundations of computer science, and Turing is the perfect figure to weave many of those narratives around. It's good for young people and the general public, and good for the field. The Turing machine is a key conceptual model for understanding the basics of computation. The Turing Test is a great model for think…

We also shouldn't underestimate the importance of truth. Dealing with the world as-it-is has better results than interacting with a story we'd like to be true but isn't.

People waste their lives in service of causes and ideas that just are not grounded in reality. Not just in the philosophical sense that we cannot know truth, but in the practical sense of "the outcome you want will not flow from the actions you are taking today". Narratives are inferior to truth when it comes to making decisions.

Re: Turing Oversold?

#60

Post by lou1306 »

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.

This dualism in CS still carries on to this day. Essentially, the lambda calculus is the forefather of the functional approach to computation, while the Turing machine epitomizes the imperative paradigm.
Post reply on HN