Questions tagged [infinite-time-computability]

Filter by
Sorted by
Tagged with
0
votes
1answer
208 views

What is the smallest countable limit ordinal in which 'lost melodies' occur

The question is in the title. This question is in response to the following paragraph found at the end of Prof. Hamkins' answer to my MathOverflow question, Are ITTM's necessary to compute Turing's &...
3
votes
2answers
400 views

Are ITTM's necessary to compute Turing's “computable numbers” and what does that mean for ordinary recursion theory?

In his celebrated paper, "On Computable Numbers, With An Application To the Entscheidungsproblem", Turing defines a "computable number" as follows: The "computable" ...
4
votes
2answers
324 views

How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence). Then the ...
0
votes
2answers
658 views

Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?

In their arXiv preprint, "Infinite Time Turing Machines" (arXiv:math/9808093v1 [math.LO] 21 Aug 1998) Hamkins and Lewis state the Lost Melody Theorem for ITTM's as follows: Lost Melody ...
6
votes
1answer
409 views

Infinite-time Turing machines and the formal Church's thesis

Infinite-time Turing machines are known to either halt or loop in countable time. In the spirit of double-negation translation, is there a statement which is: classically equivalent to this; ...
5
votes
1answer
489 views

On a characterization of the recursively inaccessible ordinals

For a given set of numbers $A$, let $O^A$ be the hyperjump of $A$. It is possible to iterate inductively the hyperjump of a set, through the computable ordinals, in a way that the $\alpha$-th ...
1
vote
0answers
130 views

A Question Regarding Productive Sets in the Koepke-Koerwien System SO (Sets of Ordinals)

In their paper "The Theory of Sets of Ordinals" (arXiv), Koepke and Koerwien propose a theory SO axiomatizing the class of sets of ordinals in a model of ZFC and show that SO and ZFC are bi-...
7
votes
1answer
380 views

A Question Regarding the Relation Between 0-sharp and Koepke's Bounded Truth Predicate.

In Jech's SET THEORY (a very early edition to which I have access), it is shown that the existence of 0-sharp implies the existence of a truth definition for the constructible universe L. Does the ...