Physical Computational Complexity and First-order Logic

DOI10.3233/FI-2021-2054OpenAlexW3188570942MaRDI QIDQ5158662

Richard Whyman

Publication date: 25 October 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2054

zbMATH Keywords

computable analysishypercomputationphysical computationBlum-Shub-Smale machinesnon-causal computationatemporal computationthe Church-Turing thesis

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
• Probabilistic logic
• The complexity of analog computation
• Unconventional complexity measures for unconventional computers
• When does a physical system compute?
• Picturing Quantum Processes
• Theory of Formal Systems. (AM-47)
• Ordinal computations
• Successor Axioms for the Integers
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Infinite time Turing machines
• Computational tameness of classical non-causal models
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Computational Complexity
• Paths, Trees, and Flowers
• Sequential abstract-state machines capture sequential algorithms
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The completeness of the first-order functional calculus

This page was built for publication: Physical Computational Complexity and First-order Logic