Physical Computational Complexity and First-order Logic
From MaRDI portal
Publication:5158662
DOI10.3233/FI-2021-2054OpenAlexW3188570942MaRDI QIDQ5158662
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
computable analysishypercomputationphysical computationBlum-Shub-Smale machinesnon-causal computationatemporal computationthe Church-Turing thesis
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