Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
DOI10.1016/J.TCS.2008.09.050zbMATH Open1160.68013DBLPjournals/tcs/Welch09OpenAlexW2050766716WikidataQ55968655 ScholiaQ55968655MaRDI QIDQ1004086FDOQ1004086
Authors: J. Martínez 
Publication date: 2 March 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.050
Recommendations
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)
Cites Work
- Deciding Arithmetic Using SAD Computers
- Title not available (Why is that?)
- Non-Turing computations via Malament--Hogarth space-times
- Recursive Functionals and Quantifiers of Finite Types I
- Subsystems of second order arithmetic
- The truth is never simple
- The fine structure of the constructible hierarchy
- Descriptive set theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classical recursion theory. The theory of functions and sets of natural numbers
- The Extent of Computation in Malament–Hogarth Spacetimes
- Recent Advances in Ordinal Analysis: Π12— CA and Related Systems
- Infinite time Turing machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classical and new paradigms of computation and their complexity hierarchies. Papers of the conference ``Foundations of the formal sciences III, Vienna, Austria, September 21-24, 2001.
- Infinite time Turing machines with only one tape
- Post's problem for supertasks has both positive and negative solutions
- Title not available (Why is that?)
- A fine hierarchy of partition cardinals
- Revision sequences and computers with an infinite amount of time
- Title not available (Why is that?)
- Set-theoretic absoluteness and the revision theory of truth
- P ≠ NP ∩ co-NP for Infinite Time Turing Machines
- Parameter-free uniformisation
- Title not available (Why is that?)
- The Length of Infinite Time Turing Machine Computations
- Eventually infinite time Turing machine degrees: infinite time decidable reals
- New Computational Paradigms
Cited In (21)
- Clockability for ordinal Turing machines
- Hypermachines
- Symmetry for transfinite computability
- Properties of stabilizing computations
- Title not available (Why is that?)
- Admissibles in gaps
- New Computational Paradigms
- Characterisations of variant transfinite computational models: Infinite time Turing, ordinal time Turing, and Blum–Shub–Smale machines
- Title not available (Why is that?)
- The computational strengths of \(\alpha\)-tape infinite time Turing machines
- Some observations on truth hierarchies
- Decision times of infinite computations
- Bounding lemmata for non-deterministic halting times of transfinite Turing machines
- Discrete transfinite computation models
- RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY
- Taming Koepke's zoo. II: Register machines
- Infinite time busy beavers
- The recognizability strength of infinite time Turing machines with ordinal parameters
- Halting time is predictable for large models: a universality property and average-case analysis
- Weaker variants of infinite time Turing machines
- Infinite time Turing machines with only one tape
This page was built for publication: Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1004086)
