Verónica Becher

A highly random number

2001, Combinatorics, Computability and Logic: Proceedings of the Third …, 2001
Citas: 31
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones

Autor(es)

Verónica Becher and Sergio Daicz and Gregory Chaitin

URL Pública

https://link.springer.com/chapter/10.1007/978-1-4471-0717-0_6

Abstract

In his celebrated 1936 paper Turing defined a machine to be circular iff it performs an infinite computation outputting only finitely many symbols. We define α as the probability that an arbitrary machine be circular and we prove that α is a random number that goes beyond Ω, the probability that a universal self delimiting machine halts. The algorithmic complexity of α is strictly greater than that of Ω, but similar to the algorithmic complexity of Ω', the halting probability of an oracle machine. What makes α interesting is that it is an example of a highly random number definable without considering oracles.

Plot de citas