Foundational results about what can and cannot be computed and how languages are classified. The halting problem shows that no program can decide, for every program and input, whether it will finish, and the Church-Turing thesis ties the idea of an effective procedure to the Turing machine. The Chomsky hierarchy ranks classes of formal grammars, the Curry-Howard correspondence links programs to proofs, and Kolmogorov complexity measures the shortest program that can produce a given object.
Browse By
Computability Theory and Formal Languages
Filter Results5 entries
Sources
Halting problem, Wikipedia
Has Member: Halting Problem, LeadQuote, Has Member: Halting Problem, Lead
In computability theory, the halting problem is the decision problem of, given an arbitrary computer program and an input, determining whether said program will eventually finish running and halt, or will continue to run forever.
Church-Turing thesis, Wikipedia
Has Member: Church-Turing Thesis, LeadQuote, Has Member: Church-Turing Thesis, Lead
In computability theory, the Church-Turing thesis is a thesis about the nature of computable functions.
Wikipedia: Chomsky hierarchy
Has Member: Chomsky Hierarchy, LeadQuote, Has Member: Chomsky Hierarchy, Lead
The Chomsky hierarchy in the fields of formal language theory, computer science, and linguistics, is a containment hierarchy of classes of formal grammars.
Wikipedia: Curry-Howard correspondence
Has Member: Curry-Howard Correspondence, LeadQuote, Has Member: Curry-Howard Correspondence, Lead
In programming language theory and proof theory, the Curry-Howard correspondence is a direct relationship between computer programs and mathematical proofs.
Kolmogorov Complexity (Wikipedia)
Has Member: Kolmogorov complexity, LeadQuote, Has Member: Kolmogorov complexity, Lead
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.