Infinite time Turing machines

被引：156

作者：

Hamkins, JD ^{[1
]}

Lewis, A

机构：

[1] CUNY Coll Staten Isl, Dept Math, Staten Isl, NY 10314 USA

[2] Virginia Commonwealth Univ, Dept Math, Richmond, VA 23284 USA

来源：

JOURNAL OF SYMBOLIC LOGIC | 2000年 / 65卷 / 02期

关键词：

D O I：

10.2307/2586556

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

we extend in a natural way the operation of raring machines to infinite ordinal time. and investigate the resulting supertask theory of computability and decidability on the reals. Every Pi(1)(1) set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the Delta(2)(1) sets. Our oracle concept leads to a notion of relative computability For sets of reals and a rich degree structure, stratified by two natural jump operators.

引用

页码：567 / 604

页数：38

共 12 条

[1] ARWISE J, 1990, ADMISSIBLE SET THEOR
[2] DUBOSE DA, 1980, J SYMBOLIC LOGIC, V55, P502
[3] FOREVER IS A DAY - SUPERTASKS IN PITOWSKY AND MALAMENT-HOGARTH SPACETIMES
EARMAN, J
NORTON, JD
[J]. PHILOSOPHY OF SCIENCE, 1993, 60 (01) : 22 - 42
[4] Earman John., 1995, BANGS CRUNCHES WHIMP
[5] FEFERMAN S, 1962, J SYMBOLIC LOGIC, V27, P383
[6] HOGARTH, 1992, FDN PHYSICS LETT, V5, P173
[7] HOGARTH, PSA, V1, P126
[8] Moschovakis Yiannis N., 1980, Descriptive Set Theory
[9] PITOWSKY, 1990, IYYUN, V39, P81
[10] SDACKS GE, 1990, HIGHER RECURSION THE

← 1 2 →