Post’s problem for ordinal register machines

Authors
Publication date 2007
Host editors
  • S.B. Cooper
  • B. Löwe
  • A. Sorbi
Book title Computation and Logic in the Real World
Book subtitle Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007 : proceedings
ISBN
  • 9783540730002
ISBN (electronic)
  • 9783540730019
Series Lecture Notes in Computer Science
Event Third Conference of Computability in Europe CiE 2007
Pages (from-to) 358-367
Publisher Berlin: Springer
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract We study Post’s Problem for the ordinal register machines defined in [6], showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors the results in [3] for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.
Document type Conference contribution
Language English
Published at https://doi.org/10.1007/978-3-540-73001-9_37
Permalink to this page
Back