Tree Representations via Ordinal Machines
Abstract
We study sets of reals computable by ordinal Turing machines with a tape of length the ordinals that are steered by a standard Turing program. The machines halt at some ordinal time or diverge. We construct tree representations for ordinal semi-decidable sets of reals from ordinal computations. The aim is to generalize uniformization results to classes of sets which are semi-decidable by computations with input-dependent bounds on the halting time. We further briefly examine the jump structure and nondeterminism.
