Log in

Relevant bibliographies by topics / Halting probability

Contents

Journal articles
Dissertations / Theses
Book chapters

Academic literature on the topic 'Halting probability'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Halting probability.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Halting probability"

1

DOWNEY, ROD, DENIS R. HIRSCHFELDT, JOSEPH S. MILLER, and ANDRÉ NIES. "RELATIVIZING CHAITIN'S HALTING PROBABILITY." Journal of Mathematical Logic 05, no. 02 (2005): 167–92. http://dx.doi.org/10.1142/s0219061305000468.

Full text

Abstract:

As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory and this Omega operator. But unlike the jump, which is invariant (up to computable permutation) under the choice of an e

APA, Harvard, Vancouver, ISO, and other styles

2

TADAKI, Kohtaro. "A generalization of Chaitin's halting probability $\Omega$ and halting self-similar sets." Hokkaido Mathematical Journal 31, no. 1 (2002): 219–53. http://dx.doi.org/10.14492/hokmj/1350911778.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

D’Abramo, Germano. "Asymptotic behavior and halting probability of Turing Machines." Chaos, Solitons & Fractals 37, no. 1 (2008): 210–14. http://dx.doi.org/10.1016/j.chaos.2006.08.022.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

CACM Staff. "The halting problem in the clear light of probability." Communications of the ACM 55, no. 6 (2012): 6–7. http://dx.doi.org/10.1145/2184319.2184321.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Chaitin, Gregory. "The Halting Probability Omega: Irreducible Complexity in Pure Mathematics." Milan Journal of Mathematics 75, no. 1 (2007): 291–304. http://dx.doi.org/10.1007/s00032-006-0064-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Becher, VeróNica, Santiago Figueira, Serge Grigorieff, and Joseph S. Miller. "Randomness and halting probabilities." Journal of Symbolic Logic 71, no. 4 (2006): 1411–30. http://dx.doi.org/10.2178/jsl/1164060463.

Full text

Abstract:

AbstractWe consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows:• ΩU[X] is random whenever X is Σn0-complete or Πn0-complete for some n ≥ 2.• However, for n ≥ 2, ΩU[X] is not n-random when X is Σn0 or Πn0. Nevertheless, there exists Δn+10 sets such that ΩU[X] is n-random.• There are Δ20 sets X such that ΩU[X] is rational. Also, for every n ≥ 1, there exists a set X which is Δn+10 and Σn0-hard such that ΩU[X] is not random.We also look at the range of ΩU as an operator. We prove

APA, Harvard, Vancouver, ISO, and other styles

7

Barmpalias, George, and Andrew E. M. Lewis. "Chaitin's halting probability and the compression of strings using oracles." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, no. 2134 (2011): 2912–26. http://dx.doi.org/10.1098/rspa.2011.0031.

Full text

Abstract:

If a computer is given access to an oracle—the characteristic function of a set whose membership relation may or may not be algorithmically calculable—this may dramatically affect its ability to compress information and to determine structure in strings, which might otherwise appear random. This leads to the basic question, ‘given an oracle A , how many oracles can compress information at most as well as A ?’ This question can be formalized using Kolmogorov complexity. We say that B ≤ LK A if there exists a constant c such that K A ( σ )< K B ( σ )+ c for all strings σ , where K X denotes t

APA, Harvard, Vancouver, ISO, and other styles

8

Barmpalias, George, and David L. Dowe. "Universality probability of a prefix-free machine." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 370, no. 1971 (2012): 3488–511. http://dx.doi.org/10.1098/rsta.2011.0319.

Full text

Abstract:

We study the notion of universality probability of a universal prefix-free machine, as introduced by C. S. Wallace. We show that it is random relative to the third iterate of the halting problem and determine its Turing degree and its place in the arithmetical hierarchy of complexity. Furthermore, we give a computational characterization of the real numbers that are universality probabilities of universal prefix-free machines.

APA, Harvard, Vancouver, ISO, and other styles

9

Hamkins, Joel David, and Alexei Miasnikov. "The Halting Problem Is Decidable on a Set of Asymptotic Probability One." Notre Dame Journal of Formal Logic 47, no. 4 (2006): 515–24. http://dx.doi.org/10.1305/ndjfl/1168352664.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Miyadera, Takayuki, and Masanori Ohya. "On Halting Process of Quantum Turing Machine." Open Systems & Information Dynamics 12, no. 03 (2005): 261–64. http://dx.doi.org/10.1007/s11080-005-0923-2.

Full text

Abstract:

We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, cannot avoid the notion of halting to be probabilistic in Quantum Turing Machine.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Halting probability"

1

Ardestani, Arash Khani. "Asynchronous cellular automata - special networks local slowdown produces global speedup." [Tampa, Fla] : University of South Florida, 2009. http://purl.fcla.edu/usf/dc/et/SFE0002814.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Skystedt, Hanna, and Otto Moen. "Kostens inverkan på halten fungicidrester i kroppen : En Bayesiansk multilevelanalys." Thesis, Linköpings universitet, Statistik och maskininlärning, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-167843.

Full text

Abstract:

Today a growing number of people are transitioning to a more plant based diet. At the same time plant basedproducts often contain higher residue levels of pesticides compared to products derived from animals. Consumingmore plant based food could therefore be seen as a potential health risk. The pilot study The ClimateFriendly and Ecological Food on Microbiota (CLEAR) from 2017 examined the relationship between diet andpesticides. The 30 participants were assigned to one of three groups: control, climate-friendly and ecological.During the study the participants were at three occasions asked to

APA, Harvard, Vancouver, ISO, and other styles

3

Bédard, Charles Alexandre. "L'information algorithmique en physique : émergence, sophistication et localité quantique." Thèse, 2020. http://hdl.handle.net/1866/23473.

Full text

Abstract:

Cette thèse explore des aspects du monde naturel par la lentille de l'information algorithmique. La notion de l'émergence, intuitivement reliée à tant de phénomènes naturels, se voit offrir une définition cadrée dans le domaine plus spécifique des statistiques algorithmiques. Capturant toutes deux l'organisation non triviale d'un objet, la sophistication et la profondeur logique sont relativisées à un objet auxiliaire puis remises en relation. Enfin, des modèles proposant une description locale des systèmes quantiques sont démontrés équivalents, ont leur coût de description quantifié et sont g

APA, Harvard, Vancouver, ISO, and other styles

4

Xiao, Yi-Jun. "Contributions aux méthodes arithmétiques pour la simulation accélérée." Phd thesis, 1990. http://pastel.archives-ouvertes.fr/pastel-00574113.

Full text

Abstract:

Cette thèse porte sur les irrégularités de distribution de suites à une ou plusieurs dimensions et sur leurs applications a l'intégration numérique. Elle comprend trois parties. La première partie est consacrée aux suites unidimensionnelles : estimations de la diaphonie de la suite de Van der Corput à partir de l'étude des sommes exponentielles et étude des suites (n). La deuxième partie porte sur quelques suites classiques en dimension plus grande que une (suites de Fame, suites de Halton). La troisième partie, consacrée aux applications à l'intégration contient de nombreux résultats numériqu

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Halting probability"

1

Svozil, K. "Halting probability amplitude of quantum computers." In J.UCS The Journal of Universal Computer Science. Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/978-3-642-80350-5_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Chaitin, Gregory J. "An Algebraic Equation for the Halting Probability." In Computerkultur. Springer Vienna, 1995. http://dx.doi.org/10.1007/978-3-7091-6597-3_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Langdon, W. B., and R. Poli. "The Halting Probability in Von Neumann Architectures." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11729976_20.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

"Leibniz, randomness & the halting probability." In Thinking about Gödel and Turing. WORLD SCIENTIFIC, 2007. http://dx.doi.org/10.1142/9789812708977_0015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

"The halting probability Ω: Concentrated creativity." In Thinking about Gödel and Turing. WORLD SCIENTIFIC, 2007. http://dx.doi.org/10.1142/9789812708977_0024.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Chaitin, Gregory J. "AN ALGEBRAIC EQUATION FOR THE HALTING PROBABILITY." In Information, Randomness & Incompleteness. WORLD SCIENTIFIC, 1987. http://dx.doi.org/10.1142/9789814434058_0008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

"The halting probability Ω: Irreducible complexity in pure mathematics." In Thinking about Gödel and Turing. WORLD SCIENTIFIC, 2007. http://dx.doi.org/10.1142/9789812708977_0023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!