Abstract

Alan Turing is one of the greatest mathematicians of the 20th century, as well as the founding father of computer science. I am therefore very proud to have received the ACM award that bears his name. However, rather than talk about the work that earned me this accolade, I'm going to tell you a surprising story: in Turing's foundational 1936 paper, in which he introduced what is known today as the Turing machine, he gave an inappropriate definition for computable real numbers. Indeed, according to his definition, multiplication by three and addition would not be computable! But alas, even with the contemporary standard definition of computable real numbers, testing for equality to zero remains undecidable. All of this is related to the fascinating intuitionistic mathematics of Brouwer, about which I shall not presume any prior knowledge.

This is joint work with Sophie Berthelette and Xavier Coiteux-Roy and published open access at https://doi.org/10.1016/j.tcs.2024.114573.

Biography

Professor of computer science at the Université de Montréal since 1979, Gilles Brassard laid the foundations of quantum cryptography at a time when nobody could have predicted that the quantum information revolution would usher in a multi-billion-dollar industry, much less that the United Nations would proclaim 2025 to be the International Year of Quantum Science and Technology and that the ACM would grant him the Turing Award for this work. Professor Brassard is also among the inventors of quantum teleportation, which is one of the most fundamental pillars of the theory of quantum information. Fellow of the Royal Society of London, Officer of the Order of Canada and Ordre national du Québec, his many accolades include the Wolf Prize in Physics, the Micius Quantum Prize, the BBVA Foundation Frontiers of Knowledge Award in Basic Sciences and the Breakthrough Prize in Fundamental Physics, in addition to the Turing Award. He has been granted honorary doctorates from ETH Zürich, the University of Ottawa, Università della Svizzera italiana in Lugano, and now the University of Waterloo.

• 报名二维码