The Church-Turing Thesis: Story and Recent Progress

Google Tech Talk
June 8, 2009

ABSTRACT

Presented by Yuri Gurevich.

The Church-Turing thesis is one of the foundations of computer science. The thesis heralded the dawn of the computer revolution by enabling the construct of the universal Turing machine which led the way, at least conceptually, to the von Neumann architecture and first electronic computers. One way to state the Church-Turing thesis is as follows:

A Turing Machine computes every numerical function that is computable by means of a purely mechanical procedure.

It is that remarkable and a priori implausible characterization that underlies the ubiquitous applicability of digital computers. But why do we believe the thesis? Careful analysis shows that the existing arguments are insufficient. Kurt Gödel surmised that it might be possible to state axioms which embody the generally accepted properties of computability, and to prove the thesis on that basis. That is exactly what we did in a recent paper with Nachum Dershowitz of Tel Aviv University.

Beyond our proof, the story of the Church-Turing thesis is fascinating and scattered in specialized and often obscure publications. I will try to do justice to that intellectual drama.

Yuri Gurevich is Principal Researcher at Microsoft Research in Redmond, WA. He is also Prof. Emeritus at the University of Michigan, ACM Fellow, Guggenheim Fellow, a member of Academia Europaea, and Dr. Honoris Causa of a couple of universities.

Category:

Science & Technology

Tags:

• google
• tech
• talk
• church-turing
• mathematics

[makeiteasyable]

ty

[weywey3318]

In the original paper Church used the phrase 'intuitivly computable' did he not? So his thesis does not actually take us from intuitions to fact, but rather from intuitions to a definition of what computable is. Is Church's Thesis not a thesis exactly because it is about intuitions? So define Turing Machines and Church Computations all you want, but there is still something to be gained by not pigeonholing our intuituions of what general computability is just yet.

[weywey3318]

I would appreciate it if computer scientists stopped using the word computability all together. Sometimes people claim to more clearly understand computation when realy they have only more clearly understood Turing Machines. This kind of thinking is dangerous. Define computation once and for all. If we dont we risk making false assumptions about our Turing Machines by extending to them conotations which belong only to the ambiguously defined word 'computation'.

[doemijmaarfriet]

Love the Lecture, but how many videos do we need to endure before remote viewers at the moment of recording are able to screw up the sound? I have seen now at least 3 great talks destroyed by chatting viewers. Keep recording, but PLEASE, fix the audio. How F@#@# hard can it be? thx.

[shtole]

I like their accents :)

[eliteg33k]

May be its just me, but I somehow felt that the lecture was about Abstract State Machines, that is the "Recent progress" part of the title.

[foobar1968]

you missed a good joke at 34:05... ;)

[someman7]

the fact that I managed to watch it untill 33rd minute testifies to my will power. :-P

[doupz0r]

sounds like a problem with your will power, not the video.

[someman7]

I understand that, but since the "intro" was longer than the actual thing, and made an otherwise interesting subject boring to me, I didn't have enough will power to continue.