Hubbry Logo
Decider (Turing machine)Decider (Turing machine)Main
Open search
Decider (Turing machine)
Community hub
Decider (Turing machine)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Decider (Turing machine)
Decider (Turing machine)
Decider (Turing machine)
View on Wikipedia
from Wikipedia
Turing machines
Machine
Variants
Science

In computability theory, a decider is a Turing machine that halts for every input.[1] A decider is also called a total Turing machine[2] as it represents a total function.

Because it always halts, such a machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is the set of recursive languages.

Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem. This is a variant of the halting problem, which asks for whether a Turing machine halts on a specific input.

Functions computable by total Turing machines

[edit]
Main article: Computable function

In practice, many functions of interest are computable by machines that always halt. A machine that uses only finite memory on any particular input can be forced to halt for every input by restricting its flow control capabilities so that no input will ever cause the machine to enter an infinite loop. As a trivial example, a machine implementing a finitary decision tree will always halt.

It is not required that the machine be entirely free of looping capabilities, however, to guarantee halting. If we restrict loops to be of a predictably finite size (like the FOR loop in BASIC), we can express all of the primitive recursive functions (Meyer and Ritchie, 1967). An example of such a machine is provided by the toy programming language PL-{GOTO} of Brainerd and Landweber (1974).

We can further define a programming language in which we can ensure that even more sophisticated functions always halt. For example, the Ackermann function, which is not primitive recursive, nevertheless is a total computable function computable by a term rewriting system with a reduction ordering on its arguments (Ohlebusch, 2002, pp. 67).

Despite the above examples of programming languages which guarantee termination of the programs, there exists no programming language which captures exactly the total recursive functions, i.e. the functions which can be computed by a Turing machine that always halts. This is because existence of such a programming language would be a contradiction to the non-semi-decidability of the problem whether a Turing machine halts on every input.

Relationship to partial Turing machines

[edit]

A general Turing machine will compute a partial function. Two questions can be asked about the relationship between partial Turing machines and total Turing machines:

  1. Can every partial function computable by a partial Turing machine be extended (that is, have its domain enlarged) to become a total computable function?
  2. Is it possible to change the definition of a Turing machine so that a particular class of total Turing machines, computing all the total computable functions, can be found?

The answer to each of these questions is no.

The following theorem shows that the functions computable by machines that always halt do not include extensions of all partial computable functions, which implies the first question above has a negative answer. This fact is closely related to the algorithmic unsolvability of the halting problem.

Theorem—There are Turing computable partial functions that have no extension to a total Turing computable function. In particular, the partial function f defined so that f(n) = m if and only if the Turing machine with index n halts on input 0 with output m has no extension to a total computable function.

Indeed, if g were a total computable function extending f then g would be computable by some Turing machine; fix e as the index of such a machine. Build a Turing machine M, using Kleene's recursion theorem, which on input 0 simulates the machine with index e running on an index nM for M (thus the machine M can produce an index of itself; this is the role of the recursion theorem). By assumption, this simulation will eventually return an answer. Define M[clarify] so that if g(nM) = m then the return value of M is ⁠⁠. Thus f(nM), the true return value of M on input 0, will not equal g(nM). Hence g does not extend f.

The second question asks, in essence, whether there is another reasonable model of computation which computes only total functions and computes all the total computable functions. Informally, if such a model existed then each of its computers could be simulated by a Turing machine. Thus if this new model of computation consisted of a sequence of machines, there would be a recursively enumerable sequence of Turing machines that compute total functions and so that every total computable function is computable by one of the machines Ti. This is impossible, because a machine T could be constructed such that on input i the machine T returns . This machine cannot be equivalent to any machine T on the list: suppose it were on the list at index j. Then , which does not return an integer result. Therefore, it cannot be total, but the function by construction must be total (if total functions are recursively enumerable, then this function can be constructed), which is a contradiction. This shows that the second question has a negative answer.

The set of indices of total Turing machines

[edit]
See also: Termination analysis

The decision problem of whether the Turing machine with index e will halt on every input is not decidable. In fact, this problem is at level of the arithmetical hierarchy. Thus this problem is strictly more difficult than the Halting problem, which asks whether the machine with index e halts on input 0. Intuitively, this difference in unsolvability is because each instance of the "total machine" problem represents infinitely many instances of the Halting problem.

Provability

[edit]

One may be interested not only in whether a Turing machine is total, but also in whether this can be proven in a certain logical system, such as first order Peano arithmetic.

In a sound proof system, every provably total Turing machine is indeed total, but the converse is not true: informally, for every first-order proof system that is strong enough (including Peano arithmetic), there are Turing machines which are assumed to be total, but cannot be proven as such, unless the system is inconsistent (in which case one can prove anything). The proof of their totality either rests on some assumptions or require another proof system.

Thus, as one can enumerate all the proofs in the proof system, one can build a Turing machine on input n that goes through the first n proofs and look for a contradiction. If it finds one, it gets into an infinite loop and never halts; otherwise, it halts. If the system is consistent, the Turing machine will halt on every input, but one cannot prove this in a strong enough proof system due to Gödel's incompleteness theorems.

One can also create a Turing machine that will halt if and only if the proof system is inconsistent, and is thus non-total for a consistent system but cannot be proven such: This is a Turing machine that, regardless of input, enumerates all proofs and halts on a contradiction.

A Turing machine that goes through Goodstein sequences and halts at zero is total but cannot be proven as such in Peano arithmetic.

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Decider (Turing machine)

View on Grokipedia
from Grokipedia
In computability theory, a decider is a Turing machine that halts on every possible input, definitively accepting strings in a given language and rejecting those not in it. This property distinguishes deciders from recognizers, which may loop indefinitely on inputs outside the language. The concept of a decider formalizes the notion of an algorithm that always terminates with a correct yes/no answer regarding language membership, underpinning the study of decidable languages—those for which such a machine exists. Decidable languages, also known as recursive languages, include practical problems like determining whether a deterministic finite automaton accepts a given string or checking the validity of basic arithmetic expressions. In contrast, not all languages are decidable; Alan Turing's 1936 work demonstrated the existence of undecidable problems, such as the halting problem, which asks whether a Turing machine halts on a specific input. Deciders play a foundational role in , enabling proofs of undecidability via reductions that map problems to known undecidable ones, like the . They also relate to Turing's original motivation in addressing the Entscheidungsproblem () in , where he showed that no general decider exists for logical validity. Extensions to nondeterministic Turing machines preserve the decider property if all computation branches halt.

Definition and Fundamentals

Formal Definition

In the context of Turing machines, a decider is a Turing machine MM that, for every input string ww over its input alphabet Σ\Sigma, halts after a finite number of steps and outputs either "accept" if ww is in the language L(M)L(M) recognized by MM, or "reject" if ww is not in L(M)L(M). This halting requirement distinguishes deciders from recognizers, which may loop indefinitely on some inputs. Formally, a Turing machine M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}}) is a decider for a L⊆Σ∗L \subseteq \Sigma^* if, for all w∈Σ∗w \in \Sigma^*, the computation of MM on input ww halts and M(w)M(w) returns 1 (accept) if w∈Lw \in L and 0 (reject) otherwise, where halting occurs by entering either the accept state qacceptq_{\text{accept}} or the reject state qrejectq_{\text{reject}}. Here, QQ is a of states with q0∈Qq_0 \in Q as the start state and qaccept,qreject∈Qq_{\text{accept}}, q_{\text{reject}} \in Q distinct; Σ\Sigma is the input not containing the blank ⊔\sqcup; Γ\Gamma is the tape with Σ⊆Γ\Sigma \subseteq \Gamma and ⊔∈Γ\sqcup \in \Gamma; and δ:Q×Γ→Q×Γ×{L,R}\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\} is the partial transition function specifying, for each state and tape , the next state, symbol to write, and head direction (left LL or right RR). The machine's tape is semi-infinite, initially containing the input ww followed by blanks, with the read-write head positioned at the leftmost symbol of ww. Computation proceeds deterministically via δ\delta until halting in qacceptq_{\text{accept}} or qrejectq_{\text{reject}}, ensuring the process terminates on all inputs. Consequently, the partial function computed by MM, which would otherwise be undefined on looping inputs, becomes a total function from Σ∗\Sigma^* to {0,1}\{0, 1\}, defined everywhere in its domain.

Key Properties

A decider is a that halts on every input string, either accepting or rejecting it, thereby guaranteeing termination unlike recognizers which may loop indefinitely on non-members of a language. This halting property ensures that for any input, the computation reaches a final state in finite time, providing a definitive answer about membership in the language it decides. A language over an alphabet is decidable precisely if there exists a decider for it, meaning the decider accepts exactly the strings in the language and rejects all others, halting in both cases. This equivalence ties the concept of decidability directly to the existence of such a machine, forming the foundation for classifying languages as recursive. The class of decidable languages exhibits strong closure properties, remaining closed under operations such as union, intersection, complement, concatenation, and Kleene star. For union, if Turing machines M1M_1 and M2M_2 decide languages L1L_1 and L2L_2, a new machine MM can be constructed to run M1M_1 on input ww; if M1M_1 accepts, then MM accepts, otherwise MM runs M2M_2 on ww and accepts if M2M_2 accepts or rejects otherwise—since both M1M_1 and M2M_2 halt, MM halts and decides L1∪L2L_1 \cup L_2. Similarly, for complement, if MM decides language LL, a machine M′M' runs MM on ww and accepts if MM rejects or rejects if MM accepts, thus deciding the complement L‾\overline{L} while halting due to MM's guarantee. These constructions extend analogously to intersection (run both and accept only if both accept), concatenation (run first on prefix, then second on suffix if accepted), and Kleene star (iteratively check prefixes and simulate accordingly until the full string is processed). All regular languages are decidable, as a (DFA) defining such a language can be simulated by a that mimics the DFA's state transitions on the input tape, halting to accept or reject based on the final state—since DFAs have finite states, the simulation terminates in linear time. However, the converse does not hold; for example, the {anbn∣n≥0}\{a^n b^n \mid n \geq 0\} is decidable via a that scans the input to count aa's, then verifies an equal number of bb's by crossing them off in a second pass, halting with acceptance or rejection accordingly, yet this is context-free but not regular. Deciders operate within deterministic time and space bounds, and the class of decidable languages encompasses complexity classes separated by deterministic time and space hierarchy theorems, which establish that for suitable constructible functions f(n)f(n) and g(n)g(n) with f(n)log⁡f(n)=o(g(n))f(n) \log f(n) = o(g(n)), there exist decidable languages requiring Ω(g(n))\Omega(g(n)) time or space. These hierarchies demonstrate strict inclusions among bounded deciders, highlighting the varying computational resources needed for different decidable languages without resolving the full extent of decidability.

Computability and Relations

Total versus Partial Turing Machines

In , a decider is a total for decision problems that halts on every input, thereby computing a total function defined for all possible inputs in its domain. This ensures that for decision problems, it always produces a yes or no answer by entering an accepting or rejecting state. In contrast, a partial computes a partial recursive function, which may be undefined for some inputs because the machine can loop indefinitely without halting on those cases. The primary behavioral difference arises in how these machines handle inputs: while a total Turing machine must terminate with an output on every input, a partial Turing machine may diverge (enter an ) on certain inputs outside its function's domain. For instance, consider a partial Turing machine designed to solve the , which accepts inputs corresponding to pairs (M, w) where machine M halts on input w; this machine halts and accepts on halting pairs but loops forever on non-halting ones, rendering the function partial. A total Turing machine, however, cannot exhibit such divergence and must halt—either accepting or rejecting—on all inputs, including those where the partial version would loop. Regarding expressive power, partial Turing machines can recognize a broader class of languages than total ones, specifically the recursively enumerable languages, which include sets where membership can be semi-decided (accepted if true, but possibly looping if false). Total Turing machines, by contrast, recognize only the recursive (decidable) languages, where both membership and non-membership can be decided definitively. An example is the halting set itself, which is recursively enumerable but not recursive, as no total Turing machine can decide it fully. Every total is also a partial , since halting behavior satisfies the partial computation model, but the converse does not hold: not every partial is total, due to the possibility of non-halting on some inputs. This asymmetry underscores the stricter termination requirement for deciders in .

Functions Computable by Deciders

A decider Turing machine, by definition, halts on every input and produces a yes/no output, thereby computing the of a decidable —a total recursive function valued in {0,1}. The class of such functions corresponds to the characteristic functions of recursive languages, a subclass of the total recursive functions (which are partial recursive functions defined for all inputs and computed by general total Turing machines). These general total recursive functions can be characterized as those obtainable from primitive recursive functions via closure under minimization, restricted to those that remain total. In the context of decision problems, deciders are particularly relevant for languages over a finite alphabet Σ. A language L ⊆ Σ* is decidable if there exists a decider that, on input w ∈ Σ*, outputs 1 if w ∈ L and 0 otherwise; this output corresponds exactly to the characteristic function χ_L(w) of L, which is a total recursive function. For example, every finite language is decidable, as a decider can simply check membership against a hardcoded list of strings. Similarly, every is decidable: a decider converts a given DFA or NFA to an equivalent DFA and simulates it on the input, halting with the acceptance result. Context-free languages are also decidable; the Cocke-Younger-Kasami ( provides an effective procedure to determine membership by parsing the input against a in , running in O(n^3) time for input length n. However, not every partial recursive function is total and thus computable by a decider. The canonical example is the halting function, which takes as input the description of a M and an input x, and attempts to determine if M halts on x; this function is partial recursive—computable by a that simulates M on x—but is not total, as no decider exists for the . According to the Church-Turing thesis, the total recursive functions computed by total Turing machines correspond precisely to the intuitively computable total functions, providing a foundational link between formal models of and effective procedures in and logic.

Indices and Enumeration

The Set of Total Turing Machine Indices

Turing machines admit an effective , whereby each machine is assigned a unique index e∈Ne \in \mathbb{N}, and ϕe\phi_e denotes the partial recursive function computed by the ee-th machine in this listing. The set of indices corresponding to total Turing machines—those that halt and produce an output on every input—is defined as TOT={e∈N∣ϕe is total}\mathsf{TOT} = \{ e \in \mathbb{N} \mid \phi_e \text{ is total} \}. The set TOT\mathsf{TOT} occupies the Π20\Pi_2^0 level of the arithmetic hierarchy, as the totality condition for ϕe\phi_e can be formalized arithmetically as ∀x ∃y T(e,x,y,s)\forall x \, \exists y \, T(e, x, y, s) for some computation step ss, where TT is Kleene's primitive recursive predicate verifying valid Turing machine computations. This placement implies that TOT\mathsf{TOT} is not recursive, since sets at or above the second level of the hierarchy exceed the power of total computable decision procedures. Moreover, TOT\mathsf{TOT} is Π20\Pi_2^0-complete under many-one reductions, establishing it as a canonical hard problem at this complexity level. Its complement, the set of indices for partial functions, is Σ20\Sigma_2^0-complete. Although TOT\mathsf{TOT} is infinite—owing to the existence of infinitely many distinct total recursive functions, such as the and its compositions with constants—it is sparse within the natural numbers, possessing asymptotic zero. This sparsity reflects the rarity of total behavior among the enumerable partial functions, where most indices correspond to machines that diverge on at least some inputs. The infinitude ensures non-trivial structure, but the vanishing underscores that totality is exceptional in the of all Turing machines. By , any non-trivial semantic property of the partial recursive functions computed by , including totality itself, gives rise to an undecidable . Specifically, since the of functions (no machine is total) and the full set (all machines are total) are both trivial cases, while totality is non-trivial and index-independent, membership in TOT\mathsf{TOT} cannot be decided by a . This undecidability holds even when restricting to properties like whether a machine computes a total function, confirming the foundational limits on analyzing behavior via indices.

Enumeration and Undecidability

The undecidability of the totality problem, often denoted as TOT = {e \mid \phi_e \text{ is total}}, follows from Rice's theorem, which states that any non-trivial semantic property of partial recursive functions is undecidable. The property of being total is non-trivial, as there exist indices of total functions (e.g., the constant zero function) and indices of partial functions (e.g., machines that diverge on zero). Thus, no Turing machine can decide membership in TOT. A direct proof proceeds by reduction from the halting problem, which is known to be undecidable. Assume for contradiction that a decider TT exists for TOT, which on input ee outputs "yes" if ϕe\phi_e is total and halts, or "no" otherwise. To decide if ϕe(x)\phi_e(x) halts, construct an index e′e' for a new partial function ϕe′\phi_{e'} defined as follows: for any input yy, ϕe′(y)\phi_{e'}(y) simulates ϕe(x)\phi_e(x) and halts if that simulation halts (ignoring yy). Then, ϕe′\phi_{e'} is total if and only if ϕe(x)\phi_e(x) halts, since the simulation is independent of yy. Running TT on e′e' would thus solve the halting problem, yielding a contradiction. Regarding enumeration, the set TOT is not recursively enumerable. A recursively enumerable set admits a that enumerates its members, but no such machine exists for TOT because confirming totality requires verifying halting on all inputs, which cannot be done in a dovetailed that outputs elements finitely. Dovetailing simulations of ϕe\phi_e on all inputs will show halting on finitely many inputs over time, but cannot confirm the in finite time to include ee. The complement of TOT—the set of indices of partial functions—is also not recursively enumerable, as it requires witnessing on some input, but cannot be confirmed in finite time: a non-halting after any bounded steps may still halt later, providing no finite criterion for inclusion. In the arithmetic hierarchy, TOT lies at the Π20\Pi_2^0 level, confirming its non-recursive-enumerability. The uncomputability of TOT is intimately linked to the busy beaver function Σ(n)\Sigma(n), defined as the maximum number of 1's produced by an nn-state halting Turing machine starting on a blank tape. Computing Σ(n)\Sigma(n) requires determining which nn-state machines halt on the blank tape and simulating those to completion, but this is undecidable due to the halting problem—no algorithm can reliably identify the halting subset for arbitrary nn. Conversely, the rapid growth of Σ(n)\Sigma(n)—faster than any total recursive function—underscores the barrier posed by undecidable halting checks, as even bounded simulations cannot circumvent the need to distinguish halting from non-halting behaviors. These results have profound practical implications: there exists no general to verify whether a given program halts on all inputs, rendering automatic for termination inherently limited. This limitation affects fields like and safety-critical systems, where heuristic approximations (e.g., bounded ) are used instead of exhaustive guarantees.

Provability and Implications

Provability of Totality

provides a method to encode s and logical formulas as natural numbers, enabling the formal representation of concepts within arithmetic. Under this numbering, each receives an index ee, and the predicate \Tot(e)\Tot(e) is formalized as the arithmetic sentence asserting that the machine ϕe\phi_e halts on every input, expressed as ∀x∃y T(e,x,y)\forall x \exists y \, T(e, x, y), where TT is the Kleene TT-predicate verifying computations. In Peano arithmetic (PA), the totality predicate \Tot(e)\Tot(e) is undecidable: PA cannot prove \Tot(e)\Tot(e) for every total index ee (i.e., every halting decider), nor can it prove ¬\Tot(e)\neg \Tot(e) for every partial index ee. This follows from , as \Tot(e)\Tot(e) defines a Π20\Pi^0_2-complete set, and PA fails to prove all true Π20\Pi^0_2 sentences; specifically, diagonalization constructs total machines whose totality encodes unprovable Π20\Pi^0_2 statements. Certain subclasses of total functions enjoy provable totality in weaker systems. For instance, all primitive recursive functions are provably total in (PRA), a subsystem of PA that suffices for their definition via composition and primitive ; since PA extends PRA, totality holds provably in PA as well. Oracle Turing machines equipped with a totality (access to the set TOT of total indices) can decide sets at higher levels of the arithmetic hierarchy. As TOT is Π20\Pi^0_2-complete, such machines compute all Δ30\Delta^0_3 sets, rendering previously undecidable predicates—such as those involving bounded over halting—effectively decidable relative to this . Emil Post's 1944 investigation into recursively enumerable sets and decision problems laid early groundwork for analyzing total recursive functions, highlighting their role in provability questions, building on earlier formalizations via and incompleteness results.

Role in Computability Theory

Deciders occupy a foundational position in , demarcating the precise limits of algorithmic solvability for decision problems. The class of languages decided by Turing machines, known as recursive or decidable languages, corresponds exactly to the Δ⁰₁ level of the arithmetic hierarchy, where sets are definable using a bounded number of alternations in first-order arithmetic formulas without unbounded existential or universal quantifiers beyond the decidable base. This placement highlights that deciders resolve problems at the lowest complexity tier, excluding those requiring higher quantifier alternations, such as co-recursively enumerable sets. The undecidability of the , established by Turing in , directly constrains the power of deciders by demonstrating that no can universally determine whether another machine halts on a given input, thereby limiting deciders to languages where both membership and non-membership are effectively verifiable. This result implies that while deciders handle total computable functions, many natural problems, including totality over all inputs, evade decision procedures. Deciders also contrast with recursively enumerable (RE) languages, which are semi-decidable using partial Turing machines that halt and accept on members but may loop indefinitely on non-members; the requirement for deciders to always halt ensures their languages and complements are both RE. Probabilistic extensions of deciders introduce to enhance efficiency, defining the BPP as languages decided by probabilistic Turing machines in time with probability at most 1/3, allowing amplification to arbitrarily small errors via repetition. Quantum analogues appear in , where quantum Turing machines decide languages in time with bounded , leveraging for potential exponential speedups on certain decision problems while preserving overall decidability. These extensions broaden the practical scope of decider-like computation without escaping the undecidability barriers of classical theory. Key open problems underscore the depth of deciders' role; the set TOT of indices for total Turing machines is Π²-complete, placing it above the halting problem in the arithmetic hierarchy and resisting elementary characterizations due to its universal quantification over inputs. Chaitin's Ω, the halting probability aggregating over all halting programs, is uncomputable yet left-c.e. and approximable, encoding the halting set in its binary expansion such that initial bits resolve finitely many halting instances but reveal the incompressible limits of decidability. In , deciders inform total type systems in dependently typed languages like Agda and Coq, which enforce termination to guarantee all inhabitable types yield total, decidable functions, enabling mechanized verification of program correctness.

References

  1. https://www.khoury.northeastern.edu/home/rjw/csu390-sp06/LectureMaterials/Deciders-vs-Recognizers.pdf
  2. https://cseweb.ucsd.edu/classes/sp18/cse105-ab/files/Lect17_CSE105Sp18.pdf
  3. https://courses.cs.washington.edu/courses/cse322/10au/slides/11tm-4up.pdf
  4. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
  5. https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/5b9f68b5081985b135f6ad521a93d81d_MIT6_045JS11_lec07.pdf
  6. http://www.cs.rpi.edu/~goldberg/14-CC/07-classes.pdf
  7. https://www.andrew.cmu.edu/user/ko/pdfs/lecture-12.pdf
  8. https://web.njit.edu/~marvin/cs341/notes/chap03-handout4.pdf
  9. https://www.cis.upenn.edu/~cis5110/notes/tcbook-comp.pdf
  10. https://cseweb.ucsd.edu/classes/sp18/cse105-ab/files/Lect17_CSE105Sp18_postA.pdf
  11. https://courses.grainger.illinois.edu/cs373/fa2013/Lectures/lec26.pdf
  12. https://www.arjun-chandrasekhar-teaching.com/courses/Pitt/CS1502/Lecture-Notes/Turing-Machine-Closure-Properties.pdf
  13. https://ics.uci.edu/~mikes/compsci162/archive/202302/Handouts/Unit3_part2_IntroDecidability.pdf
  14. https://www.geeksforgeeks.org/theory-of-computation/turing-machine-for-l-an-bn-n1/
  15. https://theory.cs.princeton.edu/complexity/diagchap.pdf
  16. https://www.cs.toronto.edu/~toni/Courses/438/Mynotes/page54.pdf
  17. https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf
  18. https://math.osu.edu/sites/math.osu.edu/files/Turing.pdf
  19. https://courses.grainger.illinois.edu/cs373/sp2009/lectures/lect_20.pdf
  20. https://plato.stanford.edu/entries/recursive-functions/
  21. https://www.andrew.cmu.edu/user/kk3n/complearn/chapter5.pdf
  22. https://www.cs.cmu.edu/~cdm/resources/60-arith-hier.pdf
  23. https://www.ams.org/journals/tran/1953-074-02/S0002-9947-1953-0053041-6/S0002-9947-1953-0053041-6.pdf
  24. https://arxiv.org/pdf/1109.3375
  25. http://www.cs.ucc.ie/~dgb/courses/toc/handout36.pdf
  26. https://mathworld.wolfram.com/RecursivelyEnumerableSet.html
  27. https://docs.bbchallenge.org/papers/Rado1962.pdf
  28. https://plato.stanford.edu/entries/godel-incompleteness/
  29. https://plato.stanford.edu/entries/recursive-functions/#ArithHier
  30. https://math.stackexchange.com/questions/2060919/is-the-statement-every-primitive-recursive-function-is-total-provable-in-pa
  31. http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf
  32. https://ps.uni-saarland.de/~mueck/bachelor/thesis.pdf
  33. https://ai.dmi.unibas.ch/_files/teaching/fs20/theo/slides/theory-d02-handout.pdf
  34. https://www.cs.umd.edu/users/gasarch/COURSES/452/S20/notes/dectalk.pdf
  35. https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/90f2669b06150423945715b22b48aa55_MIT6_045JS11_lec17.pdf
  36. https://www.cl.cam.ac.uk/teaching/2324/Complexity/bqp.pdf
  37. https://arxiv.org/pdf/1707.08109
  38. https://www.andrew.cmu.edu/user/liminjia/research/papers/popl10-lambda-eek.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.