Discrete transfinite computation models

DOI10.1007/978-3-319-22156-4_6zbMATH Open1301.03039arXiv1409.5052OpenAlexW1904838180MaRDI QIDQ2906573FDOQ2906573

Authors: Philip D. Welch 

Publication date: 5 September 2012

Published in: Turing’s Revolution (Search for Journal in Brave)

Abstract: We describe various computational models based initially, but not exclusively, on that of the Turing machine, that are generalized to allow for transfinitely many computational steps. Variants of such machines are considered that have longer tapes than the standard model, or that work on ordinals rather than numbers. We outline the connections between such models and the older theories of recursion in higher types, generalized recursion theory, and recursion on ordinals such as $alpha$-recursion. We conclude that, in particular, polynomial time computation on $omega$-strings is well modelled by several convergent conceptions.

Full work available at URL: https://arxiv.org/abs/1409.5052

Recommendations

• Computability and computable models
• Computability in special models
• Models and computability
• Turing Unbound: Transfinite Computation
• Models of computation
• Infinite time computable model theory
• scientific article; zbMATH DE number 804044
• Formal models of computation. The ultimate limits of computing
• Computability. Models of computation and undecidability

zbMATH Keywords

Turing machinecomputabilityconstructibilitygeneralized recursion theory

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Higher-type and set recursion theory (03D65) Turing machines and related notions (03D10) Other degrees and reducibilities in computability and recursion theory (03D30) Inner models, including constructibility, ordinal definability, and core models (03E45)

Cites Work

• A revenge-immune solution to the semantic paradoxes
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Title not available (Why is that?)
• Recursive Functionals and Quantifiers of Finite Types I
• The truth is never simple
• Title not available (Why is that?)
• A new recursion-theoretic characterization of the polytime functions
• Title not available (Why is that?)
• Trial and error predicates and the solution to a problem of Mostowski
• Splitting an α-Recursively Enumerable Set
• The recursively enumerable α-degrees are dense
• Limiting recursion
• Computability of Recursive Functions
• Infinite time Turing machines
• Notes on naive semantics
• Ultimate truth vis-à-vis stable truth
• Ordinal machines and admissible recursion theory
• Turing Computations On Ordinals
• Infinite time Turing machines with only one tape
• Post's problem for supertasks has both positive and negative solutions
• Turing-Machine Computable Functionals of Finite Types II^†
• Recursive Functionals and Quantifiers of Finite Types II
• Revision sequences and computers with an infinite amount of time
• Ordinal computations
• Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
• Eventually infinite time Turing machine degrees: infinite time decidable reals
• Post's problem for ordinal register machines: an explicit approach
• Title not available (Why is that?)
• Post's Problem, Admissible Ordinals, and Regularity
• The basic theory of infinite time register machines
• Hypermachines
• An Enhanced Theory of Infinite Time Register Machines
• A generalised dynamical system, infinite time register machines, and \(\Pi^1_1\)-\(\mathrm{CA}_{0}\)

This page was built for publication: Discrete transfinite computation models

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