Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
The Lost Melody Theorem for Infinite Time Register Machines

Edit abstract data

Speaker: Merlin Carl
Author(s): Merlin Carl and Peter Koepke
Slot: Tue, 11:40-12:00, Amphitheater B (col. 2)

Abstract

We do ordinal computability with the ITRM model proposed by Miller
and Koepke (Koepke, P., Miller, R.: An
enhanced theory of infinite time register machines. Logic and Theory
of Algorithms, Fourth Conference on Computability in Europe, CiE 2008,
Athens, Greece, June 2008, Proceedings, Lecture Notes in Computer
Science, volume 5028), with reals as oracles. A real
$\omega\in\ ^\omega\omega$ is \textbf{computable} if the function $n
\rightarrow r(n)$ is ITRM-computable from the trivial oracle and
empty input.
The singleton $\{$r$\}$ is \textbf{decidable} if there is an
ITRM-program which outputs 1 on the empty input with oracle r and 0
for any other oracle and empty input.\
In analogy with the Hamkins-Lewis "lost melody theorem" for ITTMs
(Hamkins, J.D., Lewis, A.: Infinite time Turing machines. J.
Symbolic Logic 65(2),(2000), 567-604) we prove:\
$\underline{Theorem}$: There is a real r, sucht that $\{$r$\}$ is
decidable, but r is not computable.\
The basic idea is to take r as an L-minimal code for a minimal model
of $ZF^{-}$. This involves computing the Tarski satisfaction
relation for models coded by reals and can be carried out by an ITRM
using a stack program.


websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!