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 条
  • [1] Turing Machines with Atoms
    Bojanczyk, Mikolaj
    Klin, Bartek
    Lasota, Slawomir
    Torunczyk, Szymon
    2013 28TH ANNUAL IEEE/ACM SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2013, : 183 - 192
  • [2] Zigzags in Turing Machines
    Gajardo, Anahi
    Guillon, Pierre
    COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2010, 6072 : 109 - +
  • [3] Symmetric Instruction Machines and Symmetric Turing Machines
    Burgin, Mark
    Schroeder, Marcin J.
    PHILOSOPHIES, 2025, 10 (01)
  • [4] Decision problems for Turing machines
    Finkel, Olivier
    Lecomte, Dominique
    INFORMATION PROCESSING LETTERS, 2009, 109 (23-24) : 1223 - 1226
  • [5] Composing Turing Machines in FSM
    Morazan, Marco T.
    PROCEEDINGS OF THE 2023 ACM SIGPLAN INTERNATIONAL SYMPOSIUM ON SPLASH-E, SPLASH-E 2023, 2023, : 38 - 49
  • [6] AMBIGUITY OF ω-LANGUAGES OF TURING MACHINES
    Finkel, Olivier
    LOGICAL METHODS IN COMPUTER SCIENCE, 2014, 10 (03)
  • [7] A LOCAL MODEL OF QUANTUM TURING MACHINES
    Wang, Dong-Sheng
    QUANTUM INFORMATION & COMPUTATION, 2020, 20 (3-4) : 213 - 229
  • [8] Improved simulation of nondeterministic Turing machines
    Kalyanasundaram, Subrahmanyam
    Lipton, Richard J.
    Regan, Kenneth W.
    Shokrieh, Farbod
    THEORETICAL COMPUTER SCIENCE, 2012, 417 : 66 - 73
  • [9] Verified Programming of Turing Machines in Coq
    Forster, Yannick
    Kunze, Fabian
    Wuttke, Maximilian
    CPP '20: PROCEEDINGS OF THE 9TH ACM SIGPLAN INTERNATIONAL CONFERENCE ON CERTIFIED PROGRAMS AND PROOFS, 2020, : 114 - 128
  • [10] A local model of quantum turing machines
    Wang, Dong-Sheng
    Quantum Information and Computation, 2020, 20 (3-4): : 213 - 229
12345