This talk is Yuri Gurevich's answer to Peter Shor's (famous for Shor's algorithm) comment [1] regarding a previous Gurevich work. In that previous work Dershovi

This talk is Yuri Gurevich's answer to Peter Shor's (famous for Shor's algorithm) comment [1] regarding a previous Gurevich work. In that previous work Dershovich and Gurevich prove the Church-Turing thesis formally, using an axiomatisation of what "algorithm" is, which captures the meaning assumed in Church and Turing times. But Shor complains their axiomatisation does not include probabilistic algoriths, quantum algorithms. In this talk Gurevich argues that in full generality of the term "algorithm" the thesis can not be true. 1 - https://cstheory.stackexchange.com/questions/88/what-would-it-mean-to-disprove-church-turing-thesis https://cstheory.stackexchange.com/questions/88/what-would-i...