# Randomness and degree theory for infinite time register machines

@article{Carl2016RandomnessAD, title={Randomness and degree theory for infinite time register machines}, author={Merlin Carl}, journal={Comput.}, year={2016}, volume={5}, pages={181-196} }

A concept of randomness for infinite time register machines (ITRMs) is defined and studied. In particular, we show that for this notion of randomness, computability from mutually random reals implies computability and that an analogue of van Lambalgen's theorem holds. This is then applied to obtain results on the structure of ITRM-degrees. Finally, we consider autoreducibility for ITRMs and show that randomness implies non-autoreducibility.

#### Topics from this paper

#### 4 Citations

Infinite time recognizability from generic oracles and the recognizable jump operator

- Mathematics, Computer Science
- Comput.
- 2017

A notion of relativized recognizability is introduced and it is shown that, for Infinite Time Turing Machines (ITTMs), if a real x is recognizable relative to all elements of a non-meager Borel set $Y$, then $x$ is recognizable. Expand

Some Observations on Infinitary Complexity

- Mathematics, Computer Science
- CiE
- 2018

The speedup theorem for Turing machines, which allows us to bring down the computation time and space usage of a Turing machine program down by an aribtrary positive factor under relatively mild side conditions by expanding the working alphabet does not hold for OTMs. Expand

RANDOMNESS VIA INFINITE COMPUTATION AND EFFECTIVE DESCRIPTIVE SET THEORY

- Computer Science, Mathematics
- The Journal of Symbolic Logic
- 2018

The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randoms notions defined via effective descriptive set theory such as ${\rm{\Pi }}_1^1$-randomness. Expand

Sailing Routes in the World of Computation

- Computer Science
- Lecture Notes in Computer Science
- 2018

The tutorial focuses on computably enumerable (c.e.) structures, a class that properly extends the class of all computable structures and the interplay between important constructions, concepts, and results in computability, universal algebra, and algebra. Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

Algorithmic Randomness for Infinite Time Register Machines

- Mathematics, Computer Science
- CiE
- 2014

It is shown that for this notion of randomness, computability from mutually random reals implies computability and that an analogue of van Lambalgen’s theorem holds. Expand

Infinite computations with random oracles

- Mathematics
- 2013

We consider the following problem for various infinite time machines. If a real is computable relative to large set of oracles such as a set of full measure or just of positive measure, a comeager… Expand

Turing computations on ordinals

- Mathematics, Computer Science
- Bull. Symb. Log.
- 2005

It is shown that a set of ordinals is ordinal computable from a finite set ofOrdinal parameters if and only if it is an element of Goedel's constructible universe L to prove the generalized continuum hypothesis in L. Expand

An Enhanced Theory of Infinite Time Register Machines

- Mathematics, Computer Science
- CiE
- 2008

The theory of infinite time register machines has similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis, yet they are strictly weaker than ITTMs. Expand

Algorithmic Randomness and Complexity

- Mathematics, Computer Science
- Theory and Applications of Computability
- 2010

This chapter discusses Randomness-Theoretic Weakness, Omega as an Operator, Complexity of C.E. Sets, and other Notions of Effective Randomness. Expand

Infinite Time Turing Machines

- Mathematics, Computer Science
- Minds and Machines
- 2004

Infinite time Turing machines extend the operation of ordinary Turing machines into transfinite ordinal time. By doing so, they provide a natural model of infinitary computability, a theoretical… Expand

The basic theory of infinite time register machines

- Computer Science
- Arch. Math. Log.
- 2010

This paper examines the ITRMs introduced by the third and fourth author, and introduces a notion of ITRM-clockable ordinals corresponding to the running times of computations, and proves a Lost Melody theorem. Expand

Algorithmic randomness and complexity. Theory and Applications of Computability

- Mathematics
- 2012

Where you can find the algorithmic randomness and complexity theory and applications of computability easily? Is it in the book store? On-line book store? are you sure? Keep in mind that you will… Expand

The distribution of ITRM-recognizable reals

- Mathematics, Computer Science
- Ann. Pure Appl. Log.
- 2014

It is proved that the recognizable reals of Infinite Time Register Machines have gaps in G\"odel's constructible hierarchy L, that there is no universal ITRM in terms of recognizability, and a relativized notion of Recognizability is considered. Expand

Ordinal Computability

- Mathematics, Computer Science
- CiE
- 2009

An overview of the computational strengths of *** -β -machines, where *** and β bound the time axis and the space axis of some machine model, and proves a new result on Infinite Time Register Machines. Expand