Questions tagged [infinite-time-turing-machine]
The infinite-time-turing-machine tag has no usage guidance.
3 questions
3
votes
0
answers
163
views
Why is the proof of decidability of arithmetic (Theorem 2.1) in Hamkins & Lewis (2000) enough?
Recently, I was reading the paper "Infinite Time Turing Machines" by Hamkins & Lewis. And one of the first theorems (Theorem 2.1) is about decidability of arithmetic.
The proof is quite ...
- 31
0
votes
0
answers
195
views
Does the following characterization of the elements of $\mathscr P$($\omega$) fail for ITTM's?
Hartley Rogers Jr., on pg. 120 of his text, Theory of Recursive Functions and Effective Computability, presents and discusses the following characterization of the sets in $\mathscr P(\omega)$:
$\...
- 6,132
7
votes
0
answers
471
views
Infinite time Turing machines, semi-decidable sets and descriptive set theory
Definition A set of reals $A$ is said to be ittm-eventually-semi-decidable if there is an Infinite Time Turing Machine programme $P_e$ so that $x\in A$ iff $P_e(x)$ has converged on “1” on its ...
- 4,839