14 papers · ranked by Valyu relevance
Abhinav Muraleedharan
Can a Turing Machine simulate the human mind? If the Church-Turing thesis is assumed to be true, then a Turing Machine should be able to simulate the human mind. In this paper, I challenge that assumption by providing strong mathematical arguments against the Church-Turing thesis. First, I show that there are decision…
Yair Lapin
The Turing machine halting problem can be explained by several factors, including arithmetic logic irreversibility and memory erasure, which contribute to computational uncertainty due to information loss during computation. Essentially, this means that an algorithm can only preserve information about an input, rather…
Joel David Hamkins, Theodor Nenu
| 1. | The halting problem | 2 | | --- | --- | --- | | 2. | Did Turing prove the undecidability of the halting problem? | 2 | | 3. | The prima facie case against the Turing attribution | 4 | | 4. | The circle-free problem | 5 | | 5. | The symbol-printing problem | 10 | | 6. | The Entscheidungsproblem | 12 | | 7. |…
Fernandes, Antonio Joaquim
This paper establishes an equivalence between the halting problem in computability theory and the convergence of power series in mathematical analysis. We demonstrate that for any given computer program, one can algorithmically construct a power series whose convergence behavior is equivalent to the program's halting…
Gabriel A. Melo, Marcos R. O. A. Máximo, Nei Y. Soma, Paulo A. L. Castro
'Paulo A. L. Castro'] The inner alignment problem, which asserts whether an arbitrary artificial intelligence (AI) model satisfices a non-trivial alignment function of its outputs given its inputs, is undecidable. This is rigorously proved by Rice’s theorem, which is also equivalent to a reduction to Turing’s Halting…
V. Lemus, Eduardo Acuña-Yeomans, V. Zamora, Francisco Hernández-Quiroz + 1 more
'Francisco Hernández-Quiroz' 'Héctor Zenil'] Motivated by algorithmic information theory, the problem of program discovery can help find candidates of underlying generative mechanisms of natural and artificial phenomena. The uncomputability of such inverse problem, however, significantly restricts a wider application…
Andrej Dudenhefner
> Abstract. Semi-unification is the combination of first-order unification and first-order matching. The undecidability of semi-unification has been proven by Kfoury, Tiuryn, and Urzyczyn in the 1990s by Turing reduction from Turing machine immortality (existence of a diverging configuration). The particular Turing…
Abel Luis Peralta
This is a topic in computability theory, which was first approached by Alan M. Turing in 1936 in his foundational work "On Computable Numbers". Here we face it using the Model of computability of the recursive functions instead of the Turing's machines, but the results are transferable from one to another paradigm with…
Jeff Edmonds, Ming Li
Kolmogorov complexity asks whether a string can be outputted by a Turing Machine (TM) whose description is shorter. Analogously, a real number is considered computable if a Turing machine can generate its decimal expansion. The modern $ϵ$-approximation definition of computability, widely used in practical computation…
Marius Krumm, Markus P. Müller, Michael Cuffaro, Stephan Hartmann
Can free agency be compatible with determinism? Compatibilists argue that the answer is yes, and it has been suggested that the computer science principle of “computational irreducibility” sheds light on this compatibility. It implies that there cannot, in general, be shortcuts to predict the behavior of agents…
Neha Sapkal, Nino Mancini, Divya Sthanu Kumar, Nico Spiller + 9 more
Walking is a complex motor program involving coordinated and distributed activity across the brain and the spinal cord. Halting appropriately at the correct time is a critical but often overlooked component of walking control. While recent studies have delineated specific genetically defined neuronal populations in the…
Zoe Leyva-Acosta, Eduardo Acuña Yeomans, Francisco Hernandez-Quiroz, Boris Ryabko
'Boris Ryabko'] We study practical approximations of Kolmogorov prefix complexity (K) using IMP2, a high-level programming language. Our focus is on investigating the optimality of the interpreter for this language as the reference machine for the Coding Theorem Method (CTM). This method is designed to address…
John Tromp, Marcus Hutter
We investigate how large an output can be computed by programs fitting inside a single register, using languages not designed for generating large outputs. We propose lambda calculus-based Busy Beaver functions that offer various advantages over the existing Turing machine-based ones, including a direct relation to…
Mario J. Pérez-Jiménez, Antonio Ramírez-de-Arellano, David Orellana-Martín
'David Orellana-Martín'] The security that resides in the public-key cryptosystems relies on the presumed computational hardness of mathematical problems behind the systems themselves (e.g. the semiprime factorization problem in the RSA cryptosystem), that is because there is not known any polynomial time (classical)…