Computation as an unbounded process

DOI10.1016/j.tcs.2011.12.040zbMath1279.68089MaRDI QIDQ418791

Jan van Leeuwen, Juraj 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

nondeterminism; arithmetical hierarchy; hypercomputation; mind change complexity; relativistic computation; unbounded computation

Mathematics Subject Classification ID

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

Related Items

Circular Interval-valued Computers and Simulation of (Red-green) Turing Machines, TRIAL AND ERROR MATHEMATICS I: DIALECTICAL AND QUASIDIALECTICAL SYSTEMS, P colonies. Survey, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classical recursion theory. The theory of functions and sets of natural numbers.
• \(\omega\)-computations on Turing machines
• Arithmetical hierarchy and complexity of computation
• Zeno machines and hypercomputation
• Alternation
• Iterated Limiting Recursion and the Program Minimization Problem
• Infinite time Turing machines
• Deciding Arithmetic Using SAD Computers
• The Extent of Computation in Malament–Hogarth Spacetimes
• Infinite Computations and a Hierarchy in Δ 3
• Trial and error predicates and the solution to a problem of Mostowski
• Limiting recursion
• Language identification in the limit
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Systems of Logic Based on Ordinals^†
• Recursive Predicates and Quantifiers
• Computational Complexity
• Non-Turing computations via Malament--Hogarth space-times