Asymptotic behavior and halting probability of Turing Machines

被引：0

作者：

D'Abramo, Germano ^{[1
]}

机构：

[1] Ist Nazl Astrofis, I-00133 Rome, Italy

来源：

CHAOS SOLITONS & FRACTALS | 2008年 / 37卷 / 01期

关键词：

Turing machines;

D O I：

10.1016/j.chaos.2006.08.022

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2006 Elsevier Ltd. All rights reserved.

引用

页码：210 / 214

页数：5

共 50 条

[41] Constrained Pseudorandom Functions for Turing Machines Revisited: How to Achieve Verifiability and Key Delegation
Datta, Pratish
Dutta, Ratna
Mukhopadhyay, Sourav
ALGORITHMICA, 2019, 81 (09) : 3245 - 3390
[42] Short attribute-based signatures for arbitrary Turing machines from standard assumptions
Pratish Datta
Ratna Dutta
Sourav Mukhopadhyay
Designs, Codes and Cryptography, 2023, 91 : 1845 - 1872
[43] Automata theory based on complete residuated lattice-valued logic: Turing machines
Wu, Lihua
Qiu, Daowen
Xing, Hongyan
FUZZY SETS AND SYSTEMS, 2012, 208 : 43 - 66
[44] Short attribute-based signatures for arbitrary Turing machines from standard assumptions
Datta, Pratish
Dutta, Ratna
Mukhopadhyay, Sourav
DESIGNS CODES AND CRYPTOGRAPHY, 2023, 91 (05) : 1845 - 1872
[45] Deterministic Turing machines in the range between real-time and linear-time
Klein, A
Kutrib, M
THEORETICAL COMPUTER SCIENCE, 2002, 289 (01) : 253 - 275
[46] Computational lower bounds using diagonalization: 1. Languages, Turing machines and complexity classes
Panduranga Rao M.V.
Resonance, 2009, 14 (7) : 682 - 690
[47] New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
Ibarra, Oscar H.
McQuillan, Ian
INFORMATION AND COMPUTATION, 2023, 292
[48] Computational Lower Bounds Using Diagonalization 1. Languages, Turing Machines and Complexity Classes
Rao, M. V. Panduranga
RESONANCE-JOURNAL OF SCIENCE EDUCATION, 2009, 14 (07): : 682 - 690
[49] German Encounters of Logic and Programming (1948-1958), Featuring Three Readings of Turing Machines
Bullynck, Maarten
IEEE ANNALS OF THE HISTORY OF COMPUTING, 2021, 43 (04) : 10 - 26
[50] Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families
Harumichi Nishimura
Masanao Ozawa
Quantum Information Processing, 2009, 8 : 13 - 24

← 1 2 3 4 5 →