Home Page - YouTube Channel



Computability theory - Simple English Wikipedia, the free encyclopedia

Computability theory

From the Simple English Wikipedia, the free encyclopedia that anyone can change

Computability theory is part of computer science. Scientists want to know what can be computed, and what can not.

There is a model of a computer that is used for this. It is called the Turing machine. A Turing machine basically is a special typewriter with an endless ribbon. The machine is named after the mathematician Alan Turing.

A problem is computable if it can be expressed in such a way that a Turing machine can solve it.

One of the best known examples is the Halting problem. The task is to write a program which says for all programs whether they will finally stop. This is impossible to decide. Mathematicians say the problem is undecidable.



This short article can be made longer. You can help Wikipedia by adding to it.

Wikipedia HTML 2008 in other languages
100 000 +

Česká (Czech)  •  English  •  Deutsch (German)  •  日本語 (Japanese)  •  Français (French)  •  Polski (Polish)  •  Suomi (Finnish)  •  Svenska (Swedish)  •  Nederlands (Dutch)  •  Español (Spanish)  •  Italiano (Italian)  •  Norsk (Norwegian Bokmål)  •  Português (Portuguese)  •  Română (Romanian)  •  Русский (Russian)  •  Türkçe (Turkish)  •  Українська (Ukrainian)  •  中文 (Chinese)

10 000 +

العربية (Arabic)  •  Български (Bulgarian)  •  Bosanski (Bosnian)  •  Català (Catalan)  •  Cymraeg (Welsh)  •  Dansk (Danish)  •  Ελληνικά (Greek)  •  Esperanto  •  Eesti (Estonian)  •  Euskara (Basque)  •  Galego (Galician)  •  עברית (Hebrew)  •  हिन्दी (Hindi)  •  Hrvatski (Croatian)  •  Magyar (Hungarian)  •  Ido  •  Bahasa Indonesia (Indonesian)  •  Íslenska (Icelandic)  •  Basa Jawa (Javanese)  •  한국어 (Korean)  •  Latina (Latin)  •  Lëtzebuergesch (Luxembourgish)  •  Lietuvių (Lithuanian)  •  Latviešu (Latvian)  •  Bahasa Melayu (Malay)  •  Plattdüütsch (Low Saxon)  •  Norsk (Norwegian Nynorsk)  •  فارسی (Persian)  •  Sicilianu (Sicilian)  •  Slovenčina (Slovak)  •  Slovenščina (Slovenian)  •  Српски (Serbian)  •  Basa Sunda (Sundanese)  •  தமிழ் (Tamil)  •  ไทย (Thai)  •  Tiếng Việt (Vietnamese)

1 000 +

Afrikaans  •  Asturianu (Asturian)  •  Беларуская (Belarusian)  •  Kaszëbsczi (Kashubian)  •  Frysk (Western Frisian)  •  Gaeilge (Irish)  •  Interlingua  •  Kurdî (Kurdish)  •  Kernewek (Cornish)  •  Māori  •  Bân-lâm-gú (Southern Min)  •  Occitan  •  संस्कृत (Sanskrit)  •  Scots  •  Tatarça (Tatar)  •  اردو (Urdu) Walon (Walloon)  •  יידיש (Yiddish)  •  古文/文言文 (Classical Chinese)

100 +

Nehiyaw (Cree)  •  словѣньскъ (Old Church Slavonic)  •  gutisk (Gothic)  •  ລາວ (Laos)