Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Multitape Ordinal Machines and Primitive Recursion

Edit abstract data

Speaker: Bernhard Irrgang and Benjamin Seyfferth
Author(s): Bernhard Irrgang and Benjamin Seyfferth
Slot: Tue, 12:20-12:40, Amphitheater B (col. 2)

Abstract

The $\alpha$-\textsc{Turing} machine as defined by \textsc{Peter Koepke} is a
standard \textsc{Turing} program computing on tapes of length a limit ordinal
$\alpha$ using a $\liminf$-rule to determine the machine configuration at limit
times. The machine is said to \emph{terminate} if it runs for less than
$\alpha$
many steps, otherwise it \emph{diverges}. Those machines have previously been
discussed as an underlying machine model for $\alpha$-recursion theory. We
introduce a multitape version of these machines to compute the primitive
recursive ordinal ($Prim_O$) functions which have a classical theory developed
by \textsc{Jensen} and \textsc{Karp}. Making use of that theory we prove:  
(1) If $\alpha$ is an ordinal closed under $Prim_O$ functions then $A \subseteq
\alpha$ is $\mathbf\Delta_1(L_\alpha[B])$ iff $A$ is multitape
$\alpha$-computable in $B$.
(2) A limit ordinal is admissible iff there is no multitape $\alpha$-computable
function mapping some $\beta < \alpha$ cofinally into $\alpha$.
Similar results have been discussed previously in the context of
$\alpha$-recursion theory.

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