On computable numbers, with an application to the Druckproblem

Speaker: Gilles Brassard, Université de Montréal, Canada

Abstract: In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name “printable” to real numbers that Turing originally called “computable”, we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the “computable” description of a real number to its “printable” description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective.

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. He 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 and the International Association for Cryptologic Research, International Member of the National Academy of Sciences of the United States, and Officer of the Orders of Canada and 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. He has been granted honorary doctorates from ETH Zürich, the University of Ottawa and Università della Svizzera italiana in Lugano.

Host: Prof. Stefan Wolf