# Questions tagged [infinite-time-computability]

The infinite-time-computability tag has no usage guidance.

8
questions

**0**

votes

**1**answer

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

**2**answers

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

**2**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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 ...