Computing Exact Approximations of a Chaitin Omega Number: A Glimpse of Randomness - Couverture souple

Shu, Chi-Kou

 
9783639135077: Computing Exact Approximations of a Chaitin Omega Number: A Glimpse of Randomness
Couverture souple
ISBN 10 : 3639135075 ISBN 13 : 9783639135077
Editeur : VDM Verlag, 2009

Synopsis

In this monograph,the research aimed to compute some exact bits of a Chaitin Omega number. A Chaitin Omega numbers are halting probabilities of a specific mathematical model of the ubiquitous PC called 'self- delimiting Turing machine'. In 1936,Turing showed that no mechanical procedure and therefore no formal axiomatic theory can solve Turing's halting problem, the question of whether a given computer program will eventually halt. An Omega number combines all instances of Turing's halting problem into a paradoxical real number. Its binary digits or bits are algorithmically random and cannot be distinguished from the the result of independent toss of a fair coin. Omega has a simple mathematical definition,but it does not enable us to determine more than finitely many of its digits and no other definition can do it better. Furthermore,as nobody before was able to compute any exact bit of a natural Omega number, the carrying on the computation is much more demanding than solving Turing's halting problem. We reviewed the properties of Omega numbers leading to the computation of approximations to obtain initial exact 64 bits of a Chaitin Omega number.

Les informations fournies dans la section « Synopsis » peuvent faire référence à une autre édition de ce titre.

Présentation de l'éditeur

In this monograph,the research aimed to compute some exact bits of a Chaitin Omega number. A Chaitin Omega numbers are halting probabilities of a specific mathematical model of the ubiquitous PC called 'self- delimiting Turing machine'. In 1936,Turing showed that no mechanical procedure and therefore no formal axiomatic theory can solve Turing's halting problem, the question of whether a given computer program will eventually halt. An Omega number combines all instances of Turing's halting problem into a paradoxical real number. Its binary digits or bits are algorithmically random and cannot be distinguished from the the result of independent toss of a fair coin. Omega has a simple mathematical definition,but it does not enable us to determine more than finitely many of its digits and no other definition can do it better. Furthermore,as nobody before was able to compute any exact bit of a natural Omega number, the carrying on the computation is much more demanding than solving Turing's halting problem. We reviewed the properties of Omega numbers leading to the computation of approximations to obtain initial exact 64 bits of a Chaitin Omega number.

Biographie de l'auteur

Chi-Kou Shu is a professor in the computer science college at China University of Technology. Formerly,he was an researcher at the CSIST,a national research organization in Taiwan. Dr. Shu earned the B.S. degree at Chung-Cheng institute of Technology and the M.S. degree at CSIST. He received his Ph.D. degree from The University of Auckland.

Les informations fournies dans la section « A propos du livre » peuvent faire référence à une autre édition de ce titre.

Éditeur
VDM Verlag
Date d'édition
2009
Langue
anglais
ISBN 10 
3639135075
ISBN 13 
9783639135077
Reliure
Broché
Nombre de pages
92
Coordonnées du fabricant
non disponible
Personne responsable
non disponible