Published July 2008 | Version v1
Journal article

Asymptotic behavior and halting probability of Turing Machines

  • 1. Istituto Nazionale di Astrofisica, Via Fosso del Cavaliere n. 100, 00133 Rome (Italy)

Description

Through a straightforward Bayesian approach we show that under some general conditions, a maximum running time, namely the number of discrete steps performed by a computer program during its execution, can be defined such that the probability that such a program will halt after that time is smaller than any arbitrary fixed value. Consistency with known results and consequences are also discussed

Availability note (English)

Available from http://dx.doi.org/10.1016/j.chaos.2006.08.022

Additional details

Identifiers

DOI
10.1016/j.chaos.2006.08.022;
arXiv
arXiv:math/0512390v5;
PII
S0960-0779(06)00857-5;

Publishing Information

Journal Title
Chaos, Solitons and Fractals
Journal Volume
37
Journal Issue
1
Journal Page Range
p. 210-214
ISSN
0960-0779

INIS

Country of Publication
United Kingdom
Country of Input or Organization
International Atomic Energy Agency (IAEA)
INIS RN
39048275
Subject category
S71: CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSICS;
Descriptors DEI
ASYMPTOTIC SOLUTIONS; COMPUTER CODES; PROBABILITY
Descriptors DEC
MATHEMATICAL SOLUTIONS

Optional Information

Copyright
Copyright (c) 2006 Elsevier Science B.V., Amsterdam, The Netherlands, All rights reserved.