INVESTIGADORES
BECHER veronica Andrea
capítulos de libros
Título:
A highly random number
Autor/es:
VERÓNICA BECHER; SERGIO DAICZ; GREGORY CHAITIN
Libro:
Combinatorics, Computability and Logic, C.Calude, M. J.Dineen and S.Sburlan (eds)
Editorial:
Springer
Referencias:
Año: 2001; p. 55 - 68
Resumen:
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 $alpha$ as the probability that an arbitrary machine be circular and we prove that alpha is a random number that goes beyond Omega, the probability that a universal self delimiting machine halts. The algorithmic complexity of alpha is strictly greater than that of Omega, but similar to the algorithmic complexity of Omega', the halting probability of an oracle machine. What makes alpha interesting is that it is an example of a highly random number definable without considering oracles.
