2004/12/15 by Paola Zizzi, Zizzi, Paola · 15 citations
Computer Science · Physics and Astronomy · #Computability #Computability, Logic, AI Algorithms #Computer science #FOS: Physical sciences #General Relativity and Quantum Cosmology (gr-qc) #Physics #Planck scale #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum mechanics #Scale (ratio) #Theoretical computer science #gr-qc #quant-ph
paper · pdf · doi:10.48550/arxiv.gr-qc/0412076
published in arXiv (Cornell University) (Cornell University) · 9 pages, misprints corrected, LaTeX version, accepted as contributed paper at CiE 2005
openalex publication_date 2004/12/15 · arxiv created 2005/03/07 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We consider the issue of computability at the most fundamental level of physical reality: the Planck scale. To this aim, we consider the theoretical model of a quantum computer on a non commutative space background, which is a computational model for quantum gravity. In this domain, all computable functions are the laws of physics in their most primordial form, and non computable mathematics finds no room in the physical world. Moreover, we show that a theorem that classically was considered true but non computable, at the Planck scale becomes computable but non decidable. This fact is due to the change of logic for observers in a quantum-computing universe: from standard quantum logic and classical logic, to paraconsistent logic.