Premium
Infinite Time Turing Machines With Only One Tape
Author(s) -
Hamkins Joel David,
Seabold Daniel Evan
Publication year - 2001
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200105)47:2<271::aid-malq271>3.0.co;2-6
Subject(s) - turing machine , computable function , mathematics , computable number , class (philosophy) , discrete mathematics , closing (real estate) , composition (language) , decidability , computation , computable analysis , computer science , algorithm , artificial intelligence , linguistics , philosophy , political science , law
Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi‐tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions f : ℝ → ℕ, the same class of computable functions. Nevertheless, there are infinite time computable functions f : ℝ → ℝ that are not one‐tape computable, and so the two models of infinitary computation are not equivalent. Surprisingly, the class of one‐tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal that is clockable by an infinite time Turing machine is clockable by a one‐tape machine, except certain isolated ordinals that end gaps in the clockable ordinals.