Post’s Problem for ordinal register machines: An explicit approach |
| |
| Authors: | Joel David Hamkins Russell G Miller |
| |
| Institution: | aCollege of Staten Island of The City University of New York, Mathematics Department, 2800 Victory Boulevard, Staten Island, NY 10314, USA;bThe Graduate Center of The City University of New York, Ph.D. Programs in Mathematics and in Computer Science, 365 Fifth Avenue, New York, NY 10016, USA;cQueens College of The City University of New York, Mathematics Department, 65-30 Kissena Boulevard, Flushing, NY 11367, USA |
| |
| Abstract: | We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals. |
| |
| Keywords: | Computability Ordinal computability Ordinal register machine Post’ s Problem |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
