Computation as an unbounded process

DOI10.1016/J.TCS.2011.12.040MaRDI QIDQ418791zbMATH OpenOpenAlexFDO

Authors J. Van Leeuwen, Jiří Wiedermann

Publication date 30 May 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.12.040

zbMATH Keywords

nondeterminismarithmetical hierarchyhypercomputationmind change complexityrelativistic computationunbounded computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Computational processes and incompleteness
• Turing Unbound: Transfinite Computation
• Computing with infinitely many processes
• scientific article; zbMATH DE number 6426780
• scientific article; zbMATH DE number 1909825
• Reasoning about infinite computations
• The nature of computation
• scientific article; zbMATH DE number 4154423
• Limits of computation. From a programming perspective
• Computation and its limits.

Cites work

• scientific article; zbMATH DE number 1687054 (Why is no real title available?)
• scientific article; zbMATH DE number 1103298 (Why is no real title available?)
• scientific article; zbMATH DE number 1142314 (Why is no real title available?)
• scientific article; zbMATH DE number 2013816 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1869997 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Alternation
• Arithmetical hierarchy and complexity of computation
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Computational Complexity
• Deciding Arithmetic Using SAD Computers
• Infinite Computations and a Hierarchy in Δ 3
• Infinite time Turing machines
• Iterated Limiting Recursion and the Program Minimization Problem
• Language identification in the limit
• Limiting recursion
• Non-Turing computations via Malament--Hogarth space-times
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Recursive Predicates and Quantifiers
• Systems of Logic Based on Ordinals^†
• The Extent of Computation in Malament–Hogarth Spacetimes
• Trial and error predicates and the solution to a problem of Mostowski
• Zeno machines and hypercomputation
• -computations on Turing machines

Cited in

(9)

• P colonies. Survey
• Trial and error mathematics. I: Dialectical and quasidialectical systems
• Going beyond Turing with P automata: partial adult halting and regular observer \(\omega\)-languages
• A connection between red-green Turing machines and Watson-Crick T0L systems
• Variants of P systems with activation and blocking of rules
• scientific article; zbMATH DE number 1993590 (Why is no real title available?)
• Extended spiking neural P systems with white hole rules and their red-green variants
• Circular interval-valued computers and simulation of (red-green) Turing machines
• scientific article; zbMATH DE number 4080902 (Why is no real title available?)

This page was built for publication: Computation as an unbounded process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418791)