formulasearchengine - User contributions [en]

Quantum annealing

2014-02-03T20:39:02Z

89.71.154.32: /* Implementations */

The '''kinetic Monte Carlo (KMC)''' method is a [[Monte Carlo method]] computer simulation intended to simulate the time evolution of some processes occurring in nature. Typically these are processes that occur with a given known rate. It is important to understand that these rates are inputs to the KMC algorithm, the method itself cannot predict them.

The KMC method is essentially the same as the [[dynamic Monte Carlo method]] and the [[Gillespie algorithm]].

==Algorithm==
[[Image:Transfer_rates.svg|thumb|240px|alt=Transfer rates between one initial and four final states|At each step, the system can jump into several ending states, the transfer rates between the initial state and all the possible ending states are supposed to be known.]]

The KMC algorithm for simulating the time evolution of a system where some processes can occur with known rates r can be written for instance as follows:

[[Image:State decision in KMC.svg|thumb|240px|Choice of the final state : a random var is chosen between 0 and Γtot; the probability that the system jumps into state ''i'' is proportional to Γi.]]

# Set the time <math>t = 0</math>.
# Form a list of all possible rates in the system <math>r_i</math>
# Calculate the cumulative function <math>R_i=\sum_{j=1}^i r_j</math> for <math>i=1,\ldots,N</math>, where ''N'' is the total number of transitions.
# Get a uniform random number <math>u \in (0, 1]</math>
# Find the event to carry out ''i'' by finding the ''i'' for which <math>R_{i-1} (this can be achieved efficiently using [[binary search]]).
# Carry out event ''i''.
# Get a new uniform random number <math>u^\prime \in (0, 1]</math>.
# Update the time with <math>t = t + \Delta t</math>, where <math>\Delta t = R_N^{-1} \ln(1/u^\prime)</math>
# Recalculate all rates <math>r_i</math> which may have changed due to the transition. If appropriate, remove or add new transitions ''i''. Update ''N'' and the list of events accordingly.
# Return to step 2.

(Note: because the average value of <math>\ln(1/u^\prime)</math> is equal to unity, the same ''average'' time scale can be obtained by instead using <math>\Delta t = R_N^{-1} </math> in step 8. In this case, however, the delay associated with transition ''i'' will not be drawn from the [[Poisson distribution]] described by <math>r_i</math>, but will instead be the mean of that distribution.)

This algorithm is known in different sources variously as the '''residence-time algorithm''' or the '''''n''-fold way''' or the '''Bortz-Kalos-Lebowitz (BKL)''' algorithm or just the '''kinetic Monte Carlo (KMC)''' algorithm. It is important to note that the timestep involved is a function of the probability that all events ''i'', did not occur.

==Time-dependent Algorithms==
If the rates <math>r_i(t)</math> are time dependent, step 8 has to be modified by (Prados 1997):
:<math>\int_{0}^{\Delta t} R_i(t') dt' = \ln(1/u^\prime)</math>.
The reaction (step 5) has to be chosen after this by
:<math>R_{i-1}(\Delta t) 

Another very similar algorithm is called the First Reaction Method (FRM). It consists of choosing the first-occurring reaction, meaning to choose the smallest time <math>\Delta t_i</math>, and the corresponding reaction number ''i'', from the formula
:<math>\int_{0}^{\Delta t_i} r_i(t') dt' = \ln(1/u_i) </math>,
where the <math>u_i \in (0, 1]</math> are N random numbers.

==Comments on the algorithm==
The key property of the KMC algorithm (and of the FRM one) is that if the rates are correct, if the processes associated with the rates are of the [[Poisson process]] type, and if different processes are independent (i.e. not correlated) then the KMC algorithm gives the correct time scale for the evolution of the simulated system.

If furthermore the transitions follow [[detailed balance]], the KMC algorithm can be used to simulate thermodynamic equilibrium. However, KMC is widely used to simulate non-equilibrium processes (Meng 1994), in which case detailed balance need not be obeyed.

The KMC algorithm is efficient in the sense that every iteration is guaranteed to produce a transition. However, in the form presented above it requires <math>N</math> operations for each transition, which is not too efficient. In many cases this can be much improved on by binning the same kinds of transitions into bins, and/or forming a tree data structure of the events. A constant-time scaling algorithm of this type has recently been developed and tested in (Slepoy 2008).

The major disadvantage with KMC is that all possible rates <math>r_i</math> and reactions have to be known in advance. The method itself can do nothing about predicting them.

==Examples of use==
KMC has been used in simulations of the following physical systems:
# Surface diffusion
# Surface growth (Meng 1996)
# [[Vacancy defect|Vacancy]] diffusion in alloys (this was the original use in (Young 1966))
# Coarsening of domain evolution
# Defect mobility and clustering in ion or neutron irradiated solids including, but not limited to, damage accumulation and amorphization/recrystallization models.
# Viscoelasticity of physically crosslinked networks (Baeurle 2006)

To give an idea what the "objects" and "events" may be in practice, here is one concrete simple example, corresponding to example 2 above.

Consider a system where individual atoms are deposited on a surface one at a time (typical of [[physical vapor deposition]]), but also may migrate on the surface with some known jump rate <math>w</math>. In this case the "objects" of the KMC algorithm are simply the individual atoms.

If two atoms come right next to each other, they become immobile. Then the flux of incoming atoms determines a rate ''r''deposit, and the system can be simulated with KMC considering all deposited mobile atoms which have not (yet) met a counterpart and become immobile. This way there are the following events possible at each KMC step:

* A new atom comes in with rate 'r''deposit
* An already deposited atom jumps one step with rate ''w''.

After an event has been selected and carried out with the KMC algorithm, one then needs to check whether the new or just jumped atom has become immediately adjacent to some other atom. If this has happened, the atom(s) which are now adjacent needs to be moved away from the list of mobile atoms, and correspondingly their jump events removed from the list of possible events.

Naturally in applying KMC to problems in physics and chemistry, one has to first consider whether the real system follows the assumptions underlying KMC well enough.
Real processes do not necessarily have well-defined rates, the
transition processes may be correlated, in case of atom or particle jumps
the jumps may not occur in random directions, and so on. When simulating
widely disparate time scales one also needs to consider whether
new processes may be present at longer time scales. If any of these
issues are valid, the time scale and system evolution predicted by KMC
may be skewed or even completely wrong.

==History==
The first publication which described the basic features of the KMC method (namely using a cumulative function to select an event and a time scale calculation of the form 1/''R'') was by Young and Elcock in 1966 (Young 1966). The residence-time algorithm was also published at about the same time in (Cox 1965).

Apparently independent of the work of Young and Elcock, Bortz, Kalos and Lebowitz (Bortz 1975) developed a KMC algorithm for simulating the [[Ising model]], which they called the ''n-fold way''. The basics of their algorithm is the same as that of (Young 1966), but they do provide much greater detail on the method.

The following year [[Dan Gillespie]] published what is now known as the [[Gillespie algorithm]] to describe chemical reactions (Gillespie 1976). The algorithm is similar and the time advancement scheme essentially the same as in KMC.

There is as of the writing of this (June 2006) no definitive treatise of the theory of KMC, but Fichthorn and Weinberg have discussed the theory for thermodynamic equilibrium KMC simulations in detail in (Fichthorn 1991). A good introduction is given also by Art Voter (Voter 2005),[http://www.ipam.ucla.edu/publications/matut/matut_5898_preprint.pdf] and by A.P.J. Jansen (Jansen 2003),[http://arxiv.org/abs/cond-mat/0303028],
and a recent review is (Chatterjee 2007) or (Chotia 2008).

In March, 2006 the, probably, first commercial software using Kinetic Monte Carlo to simulate the diffusion and activation/deactivation of dopants in Silicon and Silicon-like materials is released by [[Synopsys]], reported by Martin-Bragado et al. (Martin-Bragado 06).

==Varieties of KMC==
The KMC method can be subdivided by how the objects are moving or reactions
occurring. At least the following subdivisions are used:

* Lattice KMC ('''LKMC''') signifies KMC carried out on an atomic [[crystal structure|lattice]]. Often this variety is also called atomistic KMC, ('''AKMC'''). A typical example is simulation of [[vacancy (chemistry)|vacancy]] [[diffusion]] in [[alloy]]s, where a [[vacancy (chemistry)|vacancy]] is allowed to jump around the lattice with rates that depend on the local elemental composition

* Object KMC ('''OKMC''') means KMC carried out for [[crystallographic defect|defects]] or [[impurity|impurities]], which are jumping either in random or lattice-specific directions. Only the positions of the jumping objects are included in the simulation, not those of the 'background' lattice atoms. The basic KMC step is one object jump.

* Event KMC ('''EKMC''') or First-passage KMC ('''FPKMC''') signifies an OKMC variety where the following reaction between objects (e.g. clustering of two [[impurity|impurities]] or [[vacancy (chemistry)|vacancy]]-[[interstitial defect|interstitial]] annihilation) is chosen with the KMC algorithm, taking the object positions into account, and this event is then immediately carried out (Dalla Torre 2005, Oppelstrup 2006).

==External links==
* [http://www.roentzsch.org/RealBit/ 3D lattice kinetic Monte Carlo simulation in 'bit language']
* [http://www.roentzsch.org/Rayleigh/ KMC simulation of the Plateau-Rayleigh instability]
* [http://www.roentzsch.org/SurfDiff/ KMC simulation of f.c.c. vicinal (100)-surface diffusion]

==References==
* (Cox 1965): D.R. Cox and H.D. Miller, The Theory of Stochastic Processes (Methuen, London, 1965, pp 6–7.

* (Young 1966): W. M. Young and E. W. Elcock, Proceedings of the Physical Society 89 (1966) 735.

* (Bortz 1975): A. B. Bortz and M. H. Kalos and J. L. Lebowitz, Journal of Computational Physics 17 (1975) 10 [http://dx.doi.org/10.1016/0021-9991(75)90060-1 Journal of Computational Physics 17 (1975) 10] (needs subscription)

* (Gillespie 1976): D. T. Gillespie, Journal of Computational Physics 22 (1976) 403

* (Fichthorn 1991): K. A. Fichthorn and W. H. Weinberg, [http://dx.doi.org/10.1063/1.461138 Journal of Chemical Physics 95 (1991) 1090] (needs subscription)

* (Meng 1994): B. Meng and W. H. Weinberg, J. Chem. Phys. 100, 5280 (1994).

* (Meng 1996): B. Meng, W.H. Weinberg, Surface Science 364 (1996) 151-163.

* (Prados 1997): A. Prados, J. J. Brey and B. Sanchez-Rey, Journal of Statistical Physics 89, 709-734 (1997)

* (Jansen 2003): A.P.J. Jansen, An Introduction To Monte Carlo Simulations Of Surface Reactions, Condensed Matter, abstract [http://arxiv.org/abs/cond-mat/0303028 cond-mat/0303028].

* (Dalla Torre 2005): J. Dalla Torre, J.-L. Bocquet, N.V. Doan, E. Adam and A. Barbu, Phil. Mag. 85 (2005), p. 549.

* (Voter 2005): A. F. Voter, Introduction to the Kinetic Monte Carlo Method, in Radiation Effects in Solids, edited by K. E. Sickafus and E. A. Kotomin (Springer, NATO Publishing Unit, Dordrecht, The Netherlands, 2005).

* (Opplestrup 2006): T. Opplestrup, V. V. Bulatov, G. H. Gilmer, M. H. Kalos, and B. Sadigh, First-Passage Monte Carlo Algorithm: Diffusion without All the Hops, Physical Review Letters 97, 230602 (2006)

* (Chatterjee 2007): A. Chatterjee and D. G. Vlachos, An overview of spatial microscopic and accelerated kinetic Monte Carlo methods, J. Computer-Aided Mater. Des. 14, 253 (2007).

* (Chotia 2008): A. Chotia, M. Viteau, T. Vogt, D. Comparat and P. Pillet, Kinetic Monte Carlo modelling of dipole blockade in Rydberg excitation experiment, New Journal of Physics 10 pages 045031 (2008)

* (Martinez 2008): E.Martinez, J.Marian, M.H.Kalos, J.M.Perlado, Synchronous Parallel Kinetic Monte Carlo for Continuum Diffusion-Reaction Systems, Journal of Computational Physics, Volume 227, Issue 8, 1 April 2008, Pages 3804-3823

* (Martin-Bragado 2008): I. Martin-Bragado, S. Tian, M. Johnson, P. Castrillo, R. Pinacho, J. Rubio and M. Jaraiz, Modeling charged defects, dopant diffusion and activation mechanisms for TCAD simulations using kinetic Monte Carlo. [http://dx.doi.org/10.1016/j.nimb.2006.10.035 Nuclear Instruments and Methods in Physics Research B, 253 (2006) 63-67 (needs subscription).]

* (Slepoy 2008): A. Slepoy, A. P. Thompson, and S. J. Plimpton, A constant-time kinetic Monte Carlo algorithm for simulation of large biochemical reaction networks, Journal of Chemical Physics, Volume 128, Issue 20, December 2007, Page 205101

* (Baeurle 2006): S.A. Baeurle, T. Usami and A.A. Gusev, Polymer 47 (2006) 8604 [http://dx.doi.org/10.1016/j.polymer.2006.10.017].
{{Use dmy dates|date=September 2010}}

* (Serebrinsky 2011): S.A. Serebrinsky, Physical time scale in kinetic Monte Carlo simulations of continuous-time Markov chains, Physical Review E, Volume 83, Issue 3, March 2011, Paper no. 037701 [http://pre.aps.org/abstract/PRE/v83/i3/e037701 [4<nowiki>]</nowiki>]

[[Category:Monte Carlo methods]]
[[Category:Statistical mechanics]]
[[Category:Stochastic simulation]]

Euler's factorization method

2013-10-02T15:17:07Z

89.71.152.246: /* Worked example */

:''This article is a temporary experiment to see whether it is feasible and desirable to merge the articles [[Recursive set]], [[Recursive language]], [[Decidable language]], [[Decidable problem]] and [[Undecidable problem]]. Input on how best to do this is very much welcome on [[Talk:Recursive languages and sets|the article's talk page]]. This is a work in progress so the current version may seem awkward.''

In [[computability theory]], a set is '''decidable''', '''computable''', or '''recursive''' if there is an [[algorithm]] that terminates after a finite amount of time and correctly decides whether a given object belongs to the set. Decidability of a set is of particular interest when the set is viewed as a [[decision problem]]; a decidable set is also a '''decidable problem''', '''computable problem''', and '''recursive problem'''. The remainder of this article uses the term ''decidable'', although ''recursive'' and ''computable'' are equivalent in this context.

A '''language''' is a set of [[String (computer science)|finite strings]] over a particular [[Alphabet (computer science)|alphabet]]. A language is decidable (also computable, recursive) if it is a decidable set.

A set, language, or decision problem that is not decidable is '''undecidable''', '''non-recursive''', '''non-computable''', or '''uncomputable'''. There are many known undecidable sets; one of the earliest, and most famous, examples is the [[halting problem]].

Decidable sets and languages are a strict subclass of the class of [[recursively enumerable set]]s. For those sets, it is only required that there is an algorithm that correctly decides when an input ''is'' in the set; the algorithm may fail to terminate for inputs not belonging to the set.

==Formal definition==

A subset ''S'' of the [[natural numbers]] is called '''decidable''' if there exists a [[total function|total]] [[computable function]] <math>f</math> such that
<math>f(x) = 0\,</math> if <math>x \in S</math> and <math>f(x) \not = 0</math> if <math>x \notin S</math>. In other words, the set ''S'' is decidable [[if and only if]] the [[indicator function]] <math>1_{S}</math> is [[computable function|computable]].

A parallel definition applies to sets of strings over some finite alphabet; these sets are often called '''languages'''. A language is decidable if there is a computable function taking strings over the alphabet as input, which returns 0 when presented with a string not in the language, and returns 1 when presented with a string in the language.

The definition can be extended to arbitrary countable sets via [[Gödel numbering]]s. If each element of a set ''U'' has a unique associated natural number, a subset ''C'' of ''U'' is called computable if the set of natural numbers corresponding to the elements of ''C'' is decidable under the definition above. A similar definition can be made in which elements of ''U'' are identified with finite strings rather than natural numbers.

The definition can also be extended to sets of ordered pairs, ordered triples, and more generally finite sequences of objects. One way to do this is to use computable functions taking more than one argument – for example, a set ''A'' of ordered pairs of elements of a set ''X'' is decidable if there is a computable function ''g'' taking two arguments, such that for all ''x'' and ''y'' in ''X'', ''g''(''x'',''y'')= 0 if the pair (''x'',''y'') is not in ''A'', and ''g''(''x'',''y'')=1 if the pair is in ''A''. Another way of defining decidability for sets of sequences is to use a [[Cantor pairing function|pairing function]] to identify each sequence with a single object (natural number or string). Then the definitions of decidability above can be directly applied. This second method is particularly useful when the set in question contains sequences of varying lengths.

==Examples==

There are many examples of decidable sets:
* The [[empty set]] is decidable, and the entire set of natural numbers is decidable.
* Every finite or [[cofinite]] subset of the natural numbers is decidable.
* The set of [[prime number]]s is decidable.
* The finite binary strings with an even number of 1s is decidable.
* If ''f'' is a [[computable function]] then the set of pairs (''x'',''y'') such that ''f''(''x'') = ''y'' is decidable.

It is possible for a set to be decidable even if the precise algorithm that decides it is not known. For example, consider the set ''A'' containing all natural numbers ''n'' such that there is a pair of [[twin prime]]s larger than ''n''. It is not presently known whether there are infinitely many twin primes, or whether (otherwise) there is a largest pair of twin primes. But in either case, the set ''A'' is decidable. If there are infinitely many twin primes, ''A'' contains every natural number, and is thus decidable. Otherwise, there is a largest pair of twin primes, which means ''A'' is finite, and thus decidable. This means that, regardless of whether there are infinitely many twin primes, the set ''A'' is decidable, despite the fact that the correct algorithm has not been identified.

==Properties==

The class of decidable sets has numerous closure properties.
*If ''A'' is a decidable set then the [[complement (set theory)|complement]] of ''A'' is also a decidable set.
*If ''A'' and ''B'' are decidable sets then ''A'' ∩ ''B'', ''A'' ∪ ''B'', and <math>A \setminus B</math> are decidable.
* If ''A'' and ''B'' are decidable sets then ''A'' × ''B'' is decidable; this is the set of pairs (''x'',''y'') such that ''x'' is in ''A'' and ''y'' is in ''B''. Moreover, the image of ''A'' × ''B'' under the [[Cantor pairing function]] is decidable.
*The [[preimage]] of a decidable set under a [[total function|total]] [[computable function]] is a decidable set.
* The image of a decidable set under a total computable [[bijection]] is decidable.
Sets of strings have additional closure properties. If ''L'' and ''P'' are two decidable languages, then the following languages are also decidable:
* The [[Kleene star]] ''L''&lowast;. A string is in this set if and only if it can be obtained by concatenating zero or more elements of ''L'', with repetition allowed.
* The concatenation ''L''∘ ''P''. A string is in this set if and only if it can be written as an element of ''L'' followed by an element of ''P''.

Several characterizations of decidable sets are known.
* A set ''A'' is decidable if and only if both ''A'' and the [[complement (set theory)|complement]] of ''A'' are [[recursively enumerable set]]s.
* A set of natural numbers is decidable if and only if it is at level <math>\Delta^0_1</math> of the [[arithmetical hierarchy]].
* A set of natural numbers is decidable if and only if it is either the range of a nondecreasing total computable function or is the empty set. Conversely, the image of a decidable set under a nondecreasing total computable function is decidable.

==Decidable languages==

A '''decidable language''' in [[mathematics]], [[logic]] and [[computer science]], is a type of [[formal language]] which is also called '''recursive''' or '''Turing-decidable'''. Since computational problems can be formulated in terms of testing membership in a language, showing that a language is decidable is thus considered the same as showing that an equivalent computational problem is decidable.<ref>{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation, Third Edition|year=2013|publisher=Cengage Learning|location=Boston, MA|isbn=978-1-133-18779-0|page=195}}</ref> In other words, we can say that a language L is decidable if there is a [[Turing Machine]] which decides L and halts on every input (meaning it either accepts or rejects, but never enters an infinite loop). A computational problem is thus considered decidable if it can be solved by a computer.

The class of all decidable languages is often called '''[[R (complexity)|R]]''', although this name is also used for the class [[RP (complexity)|RP]]. All decidable languages are [[recursively enumerable language|recursively enumerable]], and all [[regular language|regular]], [[context-free language|context-free]] and [[context-sensitive language|context-sensitive]] languages are decidable. In other words, all languages recognized by [[Deterministic finite automaton|DFA]]’s, [[Nondeterministic finite automaton|NFA]]’s, and [[Context-free grammar|CFG]]’s are decidable. However, not all languages recognized by a [[Turing machine|TM]] are decidable. Similarly, not all languages that are recognizable are decidable.<ref>{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation, Third Edition|year=2013|publisher=Cengage Learning|location=Boston, MA|isbn=978-1-133-18779-0|page=201}}</ref>

This type of language was not defined in the [[Chomsky hierarchy]] of {{Harv|Chomsky|1959}}, and there is no simple class of [[formal grammar]]s that capture the decidable languages.{{Citation needed|date=October 2008}}

=== List of Common Decidable Languages and Problems <ref>{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation, Third Edition|year=2013|publisher=Cengage Learning|location=Boston, MA|isbn=978-1-133-18779-0|pages=194–200}}</ref> ===

<math>
A_{DFA} = \{\langle B,w \rangle \mid B \text{ is a DFA that accepts input string } w \}
</math>

<math>
A_{NFA} = \{\langle B,w \rangle \mid B \text{ is a NFA that accepts input string } w \}
</math>

<math>
A_{REX} = \{\langle R,w \rangle \mid R \text{ is a regular expression that generates string } w \}
</math>

<math>
A_{CFG} = \{\langle G,w \rangle \mid G \text{ is a CFG that generates string } w \}
</math>

<math>
E_{DFA} = \{\langle A \rangle \mid A \text{ is a DFA and } L \left( A \right)= \empty \}
</math>

<math>
EQ_{DFA} = \{\langle A, B \rangle \mid A \text { and } B \text{ are DFA's and } L \left( A \right)= L\left( B \right) \}
</math>

<math>
E_{CFG} = \{\langle G \rangle \mid G \text{ is a CFG and } L \left( G \right)= \empty \}
</math>

== Undecidability ==

A '''[[decision problem]]''' is, informally, a problem whose solution is either "yes" or "not". Each such problem is characterized by the set of inputs whose solution is "yes". As a result, decision problems are formally defined as being sets, either of strings or of natural numbers: any such set defines the problem of deciding whether a given object belongs to the set.

A decision problem ''A'' is called '''decidable''' or '''effectively solvable''' if ''A'' is a [[recursive set]], that is, there exists an algorithm for establishing the presence of the element in the set. A problem is called '''partially decidable''', '''semidecidable''', '''solvable''', or '''provable''' if ''A'' is a [[recursively enumerable set]]. Partially decidable problems and any other problems that are not decidable are called '''undecidable'''.

===The halting problem ===
{{main|Halting problem}}

In [[computability theory (computer science)|computability theory]], the '''halting problem''' is a [[decision problem]] which can be stated as follows:

:''Given a description of a [[computer program|program]] and a finite input, decide whether the program eventually halts when started with that input, or whether it runs forever..''

[[Alan Turing]] proved in 1936 that a general [[algorithm]] to solve the halting problem for ''all'' possible program-input pairs cannot exist; the set of pairs (''e'',''n'') such that the program with description ''e'' halts on input ''n'' is undecidable.

=== Decidability of logical theories ===

{{main|Decidability (logic)}}

In [[mathematical logic]], a '''[[theory (mathematical logic)|theory]]''' is a set of formal sentences that is closed under [[logical consequence]] (essentially, any sentence that can be proved from sentences in the theory is itself in the theory). Important examples are the set of all [[Peano arithmetic|arithmetical sentences]] that are satisfied by the set of [[natural numbers]], and the set of arithmetical sentences provable from the axioms of [[Peano arithmetic]].

Many formal theories have been studied in the context of decidability. For example, the theory of the real numbers (in the [[signature (logic)|signature]] of [[field (mathematics)|fields]]) is decidable, while the [[first-order logic|first-order]] theory of the natural numbers is not. [[Gödel's incompleteness theorem]] implies that no first-order theory capable of interpreting a sufficient amount of the theory of the natural numbers can be decidable.

==List of undecidable problems==

In [[computability theory]], an '''undecidable problem''' is a problem whose language is not a [[recursive set]]. More informally, such problems cannot be solved in general by computers; see [[Decidability (logic)|decidability]]. This is a list of undecidable problems. Note that there are [[uncountable set|uncountably]] many undecidable problems, so this list is necessarily incomplete. Though undecidable languages are not recursive languages, they may be a [[subset]] of [[Alan Turing|Turing]] recognizable languages.

=== Problems related to abstract machines ===

* The [[halting problem]] (determining whether a specified machine halts or runs forever).
* The [[busy beaver]] problem (determining the length of the longest halting computation among machines of a specified size).
* [[Rice's theorem]] states that for all non-trivial properties of partial functions, it is undecidable whether a machine computes a partial function with that property.

=== Other problems ===

* The [[Post correspondence problem]].
* The [[word problem for groups]].
* The [[word problem (computability)|word problem]] for certain [[formal languages]].
* The problem of determining if a given set of [[Wang tile]]s can tile the plane.
* The problem whether a [[Tag system]] halts.
* The problem of determining the [[Kolmogorov complexity]] of a string.
* Determination of the solvability of a Diophantine equation, known as [[Hilbert's tenth problem]]
* Determining whether two finite [[simplicial complex]]es are homeomorphic
* Determining whether the [[fundamental group]] of a finite simplicial complex is trivial
* Determining if a [[context-free grammar]] generates all possible strings, or if it is ambiguous.
* Given two context-free grammars, determining whether they generate the same set of strings, or whether one generates a subset of the strings generated by the other, or whether there is any string at all that both generate.

== References ==
{{Reflist}}
* {{Citation | last = Chomsky | first = Noam | year = 1959 | title = On certain formal properties of grammars | journal = Information and Control | volume = 2 | issue = 2 | pages = 137–167 | doi = 10.1016/S0019-9958(59)90362-6 | postscript = .}}
*{{ citation | author=Cutland, N. |title=Computability.|publisher=Cambridge University Press|year=1980|isbn=0-521-29465-7 }}
* {{Citation | last1=Rogers | first1=Hartley | title=The Theory of Recursive Functions and Effective Computability | origyear=1967 | publisher=First MIT press paperback edition | isbn=978-0-262-68052-3 | year=1987}}
* {{Citation|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | chapter = Decidability | pages = 151–170 | isbn = 0-534-94728-X}}
* {{Citation | last1=Soare | first1=R. | title=Recursively Enumerable Sets and Degrees | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1987}}

{{Formal languages and grammars}}

[[Category:Computability theory]]
[[Category:Theory of computation]]
[[Category:Formal languages]]