5
votes
Accepted
Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?
No, classical computability theory as you point is quite capable of dealing with infinitary computable enumerations and computability-in-the-limit from its earliest stages. I believe that Turing is to ...
- 225k
4
votes
Accepted
What is the smallest countable limit ordinal in which 'lost melodies' occur
I interpret this question as asking, what is the first ordinal $\alpha$ such that there is some lost melody (in the sense of Hamkins-Lewis Theorem 4.9) in $L_\alpha$.
The answer is $\alpha=\Sigma+1$ (...
- 27.4k
4
votes
Are ITTM's necessary to compute Turing's "computable numbers" and what does that mean for ordinary recursion theory?
It sounds like you're asking whether the following are equivalent:
$x$ is a computable infinite binary sequence in the usual sense, that is, the function $i\mapsto x(i)$ is computable.
There is an ...
- 19.3k
4
votes
Accepted
Is there a non-standard model of PA computable with infinitary computation?
To move this off the unanswered queue, the answer is yes in a very strong way.
The relevant notion is that of a PA degree. There are many equivalent definitions of PA-ness, as well as many interesting ...
- 19.3k
4
votes
Accepted
Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?
Note that reals have an odd "double role" in the ITTM setting; besides being sets of natural numbers, they are also individual inputs to type-$2$ functionals. In the latter role they are ...
- 19.3k
3
votes
Accepted
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
I will assume V=L for simplicity. Let $C$ denote the supremum of halting times for powerful enough (ordinal) programs (such as OTMs) on empty input and no parameters etc. Also, let $\eta$ be the ...
- 861
2
votes
Accepted
Can $\{x \mathrel| \text{$\varphi_{x}$ total}\}$ be deemed a "lost melody" relative to classical recursion theory?
If we disregard the model of computation we want to use, a lost melody is a decidable singleton $\{x\}$ such that the point $x$ is non-computable. Classical computability theory cannot admit any lost ...
- 4,501
2
votes
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
The ordinal is the supremum of the ordinals in the $Σ_2$ hull of $L_{ω_1}$. It is robust to the choice of the computational model as long as (uniformly in $x$) the halting problem is $Π^1_1(x)$-hard ...
- 6,112
2
votes
Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?
It was already mentioned that the "domain enumeration" property of classical Turing machines ban them from having lost melodies right away. But (as was already hinted in the comments) when ...
- 31
2
votes
Accepted
On a characterization of the recursively inaccessible ordinals
Well assuming that $\lambda^A$ is always the first recursively admissible which is bigger than $\omega_1^A$, which I think should be true, I think my question is after all not so interesting:
Either ...
- 764
Only top scored, non community-wiki answers of a minimum length are eligible