×

zbMATH — the first resource for mathematics

Hypermachines. (English) Zbl 1220.03040
Summary: The Infinite Time Turing Machine model [J. Symb. Log. 65, No. 2, 567–604 (2000; Zbl 0963.03064)] of J. D. Hamkins and A. Lewis is, in an essential sense, a “\(\Sigma _{2}\)-machine” in that it uses a \(\Sigma _{2}\) Liminf Rule to determine cell values at limit stages of time. We give a generalisation of these machines with an appropriate \(\Sigma _{n}\) rule. Such machines either halt or enter an infinite loop by stage \(\zeta (n) =_{\text{df}} \mu \zeta (n) [\exists \Sigma (n) > \zeta (n) L_{\zeta (n)} \prec _{\Sigma_n} L_{\Sigma (n)}]\), again generalising precisely the ITTM case. The collection of such machines taken together computes precisely those reals of the least model of analysis.

MSC:
03D10 Turing machines and related notions
03D65 Higher-type and set recursion theory
03E45 Inner models, including constructibility, ordinal definability, and core models
Citations:
Zbl 0963.03064
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Saving truth from paradox (2008) · Zbl 1225.03006
[2] Fine structure and class forcing 3 (2000) · Zbl 0954.03045
[3] Constructibility (1984) · Zbl 0542.03029
[4] The truth is never simple 51 pp 663– (1986)
[5] DOI: 10.1016/j.tcs.2008.09.050 · Zbl 1160.68013
[6] Eventually Infinite Time Turing degrees: infinite time decidable reals 65 pp 1193– (2000) · Zbl 0959.03025
[7] Proceedings of the 1972 Oslo symposium pp 81– (1974)
[8] Descriptive set theory (1980) · Zbl 0433.03025
[9] Cabal seminar 77–79: Proceedings of the Caltech-UCLA logic seminar 1977–1979 839 pp 33– (1981)
[10] DOI: 10.1016/0003-4843(72)90001-0 · Zbl 0257.02035
[11] The higher infinite (1994)
[12] Infinite time Turing machines 65 pp 567– (2000)
[13] Bonn International Workshop on Ordinal Computability (BIWOC 2007 Bonn) pp 44– (2007)
[14] DOI: 10.1090/S0002-9939-08-09275-7 · Zbl 1145.03030
[15] DOI: 10.1016/j.apal.2003.10.015 · Zbl 1065.03501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.