Natural Halting Probabilities, Partial Randomness, and Zeta Functions

Details Natural Halting Probabilities, Partial Randomness, and Zeta Functions Natural Halting Probabilities, Partial Randomness, and Zeta Functions

2006-06-07

arxiv.org/abs/cs/0606033v2

Computer Science

Computational Complexity

Accepted for publication in Information and Computing

Scientific paper

We introduce the zeta number, natural halting probability and natural complexity of a Turing machine and we relate them to Chaitin's Omega number, halting probability, and program-size complexity. A classification of Turing machines according to their zeta numbers is proposed: divergent, convergent and tuatara. We prove the existence of universal convergent and tuatara machines. Various results on (algorithmic) randomness and partial randomness are proved. For example, we show that the zeta number of a universal tuatara machine is c.e. and random. A new type of partial randomness, asymptotic randomness, is introduced. Finally we show that in contrast to classical (algorithmic) randomness--which cannot be naturally characterised in terms of plain complexity--asymptotic randomness admits such a characterisation.

Affiliated with

Also associated with

No associations

Rating

Natural Halting Probabilities, Partial Randomness, and Zeta Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Natural Halting Probabilities, Partial Randomness, and Zeta Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Natural Halting Probabilities, Partial Randomness, and Zeta Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-506855