The talk begins: ANNOUNCER: So it's my distinct pleasure, and privilege, to host Yuri for a talk on a topic I have discussed with him since I was even a studen

The talk begins: ANNOUNCER: So it's my distinct pleasure, and privilege, to host Yuri for a talk on a topic I have discussed with him since I was even a student: models of computation. And through the years, we have interacted in various ways, on both fundamentals of models of computation and then abstract state machine applications, and at this point, it's also probably the last talk that Yuri will give at this institution, as he is moving to Michigan next week. But I have no doubts that there will be many opportunities to interact with Yuri in the future. I hear that there's a birthday party coming up in a couple of years, and it was always a pleasure to participate in these events. So, without more adieu, please go ahead. YURI: Thank you very much. It's a pleasure for return for a day. [First slide appears] >My scholarly friend Nachum Dershowitz and I published a long paper >"A natural axiomatization of computability and proof of Church's thesis", Bulletin of Symbolic Logic, 2008 >where we proved Church's thesis for classical algorithms. >Here classical is not the counterpart to quantum as is common in quantum literature. By classical algorithms we mean traditional algorithms from antiquity to Turing's time, also known as sequential algorithms. >The claim that the Church-Turing thesis cannot be true in general is implicit in: >"What is an Algorithm?" SOFSEM 2012, Springer LNCS 7147 (2012) >The main goal of this talk is to clarify things and argue for the claim. YURI: In 2008 Nachum Dershowitz, my very learned scholarly friend and myself, we wrote this paper, we proved Church's thesis, and Turing's thesis, but on very technical-- they are slight differences, it's a technicality -- for classical algorithms. Now what do we mean by classical algorithms? Now quantum people hijack the word "classical" -- it became to mean non-quantum, but our meaning was classical in the sense: algorithms from time immemorial, certainly, until 1950s, 1960s. So, this is the algorithm that Church and Turing had in mind when they put forward their theses. So, another name for these classical algorithms was traditional algorithms, or sequential. I will call them mostly sequential, because the first sort of non-classical, non-traditional algorithms were parallel, and so there was this -- there was traditional or non-sequential. You can generalize, and generalize, then it's not completely obvious why it should be even true. YURI: I had this argument implicitly published years ago, but as you see: [Second slide appears] >There is a a problem with long scholarly papers: it takes time to read them, and there is a tendency to skim. >Peter Shor: The Dershowitz-Gurevich paper says nothing about probabilistic or quantum computation. It does write down a set of axioms about computation, and prove the Church-Turing thesis assuming those axioms. However, we're left with justifying the axioms. Neither probabilistic nor quantum computation is covered by these axioms (they admit this for probabilistic computation, and do not mention quantum computation at all), so it's quite clear to me these axioms are false in the real world, even though the Church-Turing thesis is probably true. >Nov, 22, 2010. https://cstheory.stackexchange.com/questions/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/what-would-it-m... >The great hero of quantum computing has not read the paper. =========================================================== I hope this will help you decide whether or not to make time to watch the video, although I agree it would be helpful to have a complete transcription available.