In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.

Church’s Thesis, Turing’s Limits, and Deutsch’s Principle

Rossella Lupacchini
2018

Abstract

In the search for a precise definition of the notion of effective calculability, Turing’s computability has proven to be more convincing than other definitions proposed almost simultaneously. Turing does not define a particular class of “calculable functions”, but which processes can be carried out in computing. His conceptual analysis brings about an intimate and inescapable link between computability and “measurability”, hence between mechanical procedures and physical processes. The full significance of this link is captured in Deutsch’s physical version of the Church-Turing thesis, namely, his claim that every physical system can be simulated by a universal quantum Turing machine. Quantum physics supports more efficient forms of computation, even though quantum computation remains within Turing’s limits. Why? This chapter explores how logical principles and physical processes coalesce into the notion of computation.
Physical Perspectives on Computation, Computational Perspectives on Physics
60
80
Rossella Lupacchini
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/635005
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact