Category:Recursion theory

From Wikipedia, the free encyclopedia

This category is for articles about recursion theory, also called computability theory, which is a branch of mathematical logic concerned with generalizations of the notion of computable function, and with related concepts such as Turing degrees.

Related information about computability theory in computer science is described in the theory of computation article and is categorized in Category:Theory of computation

Subcategories

This category has the following 3 subcategories, out of 3 total.

E

• Effective descriptive set theory

L

• Lambda calculus

T

• Theory of computation

Pages in category "Recursion theory"

The following 88 pages are in this category, out of 88 total. Updates to this list can occasionally be delayed for a few days.

* Recursion theory List of undecidable problems A Ackermann function Algorithm characterizations Algorithm examples Alpha recursion theory Analytical hierarchy Arithmetical hierarchy Arithmetical set Automatic group Automatic semigroup B Bounded quantifier Busy beaver C Chain rule for Kolmogorov complexity Church–Turing thesis Complete numbering Computable function Computable isomorphism Computable number Computation Computation in the limit Course-of-values recursion Craig's theorem Creative and productive sets D Decision problem Description number E ELEMENTARY Effective dimension Effectively separable

E cont. Entscheidungsproblem Enumeration F Forcing (recursion theory) G Grzegorczyk hierarchy Gödel numbering for sequences H Halting problem High (computability) History of the Church-Turing thesis Hyperarithmetical theory I Interactive computation K Kleene's T predicate Kleene's recursion theorem König's lemma Kolmogorov complexity L Lambda calculus Limiting recursive Low (computability) Low basis theorem M Malament-Hogarth spacetime Many-one reduction Martin measure Maximal set McCarthy Formalism Morphological computation Μ operator Mutual recursion Myhill isomorphism theorem N Numbering (computability theory) O Oracle machine P Post correspondence problem

P cont. Post's theorem Post–Turing machine Primitive recursive function R Recursion (computer science) Recursive language Recursive languages and sets Recursive ordinal Recursive set Recursively enumerable language Recursively enumerable set Reduction (recursion theory) Reverse mathematics Richardson's theorem S Simple set Smn theorem T Tarski–Kuratowski algorithm Trakhtenbrot's theorem Truth table reduction Turing degree Turing jump Turing machine Turing machine examples Turing machine gallery Turing reduction U Utm theorem W Wang B-machine Wolfram's 2-state 3-symbol Turing machine Word problem (computability) Μ Μ-recursive function

Categories: Mathematical logic

Views

• Category
• Discussion
• Current revision

Navigation

• Main Page
• Contents
• Featured content
• Current events

Interaction

• About Wikipedia
• Community portal
• Recent changes
• Contact Wikipedia
• Donate to Wikipedia
• Help

Search

Languages

• Esperanto
• עברית
• Svenska
• Türkçe
• 中文

• This page was last modified 09:23, 6 June 2008 by Wikipedia user Alexbot. Based on work by Wikipedia user(s) JoergenB, Lambiam, Gregbard, David Shay, Hydro2, Escarbot, CBM, Mhss en, Trovatore and Ruud Koot and Anonymous user(s) of Wikipedia.
• All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
  Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a U.S. registered 501(c)(3) tax-deductible nonprofit charity.
  
• About Wikipedia
• Disclaimers

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -