3:21 p.m.
________________________________
From: decanato.inf(a)usi.ch <noreply.newsletter(a)usi.ch>
Sent: Tuesday, May 14, 2024 11:56 AM
To: Schober William <william.schober(a)usi.ch>
Subject: Informatics Seminar on Wednesday, May 22, Gilles Brassard
Università
della
Svizzera
italiana
INF
[usi]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fusi.ch&h=mBP0qzw6Uz...
[usi]
Informatics Seminar
Browser
version<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fpublished%2FINF_2024_05_22_GillesBrassard.html&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
[arrow]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fpub...
[arrow]
[main_banner]
On computable numbers, with an application to the Druckproblem
Host: Prof. Stefan Wolf
Wednesday
22.05
USI East Campus, Room D1.14
11:00 - 12:00
Gilles Brassard
Université de Montréal, Canada
[news_img]
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.<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.inf.usi.ch%2Fit%2Ffeeds%2F10852%3Futm_source%3Dnewsletter%26utm_medium%3Demail%26utm_campaign%3D20240514%26utm_content%3DINF_2024_05_22_GillesBrassard&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
Università
della
Svizzera
italiana
Quicklinks:
INF
Website<https://newsletter.usi.ch/email/n?l=http%3A%2F%2Fwww.inf.usi.ch%2F%3Futm_source%3Dnewsletter%26utm_medium%3Demail%26utm_campaign%3D20240514%26utm_content%3DINF_2024_05_22_GillesBrassard&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
INF Newsletter
Archive<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Fns_published%2Fit%2F16%3Futm_source%3Dnewsletter%26utm_medium%3Demail%26utm_campaign%3D20240514%26utm_content%3DINF_2024_05_22_GillesBrassard&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
Campus
Lugano<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.desk.usi.ch%2Fen%2Flugano-campus-map-access-facilities%3Futm_source%3Dnewsletter%26utm_medium%3Demail%26utm_campaign%3D20240514%26utm_content%3DINF_2024_05_22_GillesBrassard&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
Follow us:
[https://uikit.usi.ch/assets/base/img/icons/twitter_white.png]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Ftwitter.com%2FUSI_inf&a...
[https://uikit.usi.ch/assets/base/img/icons/twitter_black.png]
[https://uikit.usi.ch/assets/base/img/icons/facebook_white.png]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.facebook.com%2Fusiu...
[https://uikit.usi.ch/assets/base/img/icons/facebook_black.png]
[https://uikit.usi.ch/assets/base/img/icons/linkedin_white.png]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.linkedin.com%2Fscho...
[https://uikit.usi.ch/assets/base/img/icons/linkedin_black.png]
[https://uikit.usi.ch/assets/base/img/icons/youtube_white.png]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.youtube.com%2Fusiun...
[https://uikit.usi.ch/assets/base/img/icons/youtube_black.png]
[https://uikit.usi.ch/assets/base/img/icons/instagram_white.png]
<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fwww.instagram.com%2Fusi...
[https://uikit.usi.ch/assets/base/img/icons/instagram_black.png]
Unsubscribe
here<https://newsletter.usi.ch/email/n?l=https%3A%2F%2Fnewsletter.usi.ch%2Funsubscribe%2Fit%2F16%2FeyJpdiI6IlZrM2dRTW1JUGFPa2ZSbndiNEwzWFE9PSIsInZhbHVlIjoiR2ZpZkJZeDFsY0VzWnpib2tyVHE1UE9iempSUzFrb2E4NDRJQzh1WUxhST0iLCJtYWMiOiI2ZTUwMWIxMWM5ZjE3Y2M5YTJhMDg3Yjk5MTQ2NDMyMTE0N2M4MTg1YWRmYzdjYWRmNmVhMGJhNmFhZTE2YmE4IiwidGFnIjoiIn0%3D%2F3123&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
Reports
decanato.inf@usi.ch<https://newsletter.usi.ch/email/n?l=mailto%3Adecanato.inf%40usi.ch&h=mBP0qzw6Uzt1c2HMAWMK465bA3BpwApr>
