2004/10/19 by Martin Ziegler · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #quant-ph
paper · pdf · doi:10.1007/s10773-005-8984-0
published as pp.2059-2071 in International Journal of Theoretical Physics vol.44:11 (2005) · 8 pages, 1 figure; presented at Quantum Structure 2004 (Denver)
arxiv created 2004/10/19 · openalex publication_date 2005/11/01 · arxiv updated 2010/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Recent works have independently suggested that Quantum Mechanics might permit for procedures that transcend the power of Turing Machines as well as of `standard' Quantum Computers. These approaches rely on and indicate that Quantum Mechanics seems to support some infinite variant of classical parallel computing. We compare this new one with other attempts towards hypercomputation by separating 1) its principal computing capabilities from 2) realizability issues. The first are shown to coincide with recursive enumerability; the second are considered in analogy to `existence' in mathematical logic.