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 条

[21] Small Turing machines and generalized busy beaver competition
Michel, P
THEORETICAL COMPUTER SCIENCE, 2004, 326 (1-3) : 45 - 56
[22] On simulating Turing machines with matrix semigroups with integrality tests
Halava, Vesa
Niskanen, Reino
THEORETICAL COMPUTER SCIENCE, 2024, 1005
[23] Computability of the entropy of one-tape Turing machines
Jeandel, Emmanuel
31ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2014), 2014, 25 : 421 - 432
[24] BIDIMENSIONAL TURING MACHINES AS GALILEAN MODELS OF HUMAN COMPUTATION
Giunti, Marco
PROCESSES OF EMERGENCE OF SYSTEMS AND SYSTEMIC PROPERTIES: TOWARDS A GENERAL THEORY OF EMERGENCE, 2009, : 383 - 406
[25] What can we learn from universal Turing machines?
Margenstern, Maurice
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, 2022, 37 (02) : 123 - 151
[26] "Viral" Turing Machines, computation from noise and combinatorial hierarchies
Raptis, Theophanes E.
CHAOS SOLITONS & FRACTALS, 2017, 104 : 734 - 740
[27] A compiler for multi-key homomorphic signatures for Turing machines
Samarin, Somayeh Dolatnezhad
Fiore, Dario
Venturi, Daniele
Amini, Morteza
THEORETICAL COMPUTER SCIENCE, 2021, 889 : 145 - 170
[28] Turing Machines with Atoms, Constraint Satisfaction Problems, and Descriptive Complexity
Klin, Bartek
Lasota, Slawomir
Ochremiak, Joanna
Torunczyk, Szymon
PROCEEDINGS OF THE JOINT MEETING OF THE TWENTY-THIRD EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC (CSL) AND THE TWENTY-NINTH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2014,
[29] Computing power of Turing machines in the framework of unsharp quantum logic
Shang, Yun
Lu, Xian
Lu, Raqian
THEORETICAL COMPUTER SCIENCE, 2015, 598 : 2 - 14
[30] The element distinctness problem on one-tape Turing machines
Szepietowski, A
INFORMATION PROCESSING LETTERS, 1996, 59 (04) : 203 - 206

← 1 2 3 4 5 →