From Wikipedia, the free encyclopedia
Изчислимост (поддаващ се на изчисление) (на английски: computability) в информатиката е атрибут на всеки тип изчисление (на английски: computation)[1][2], което включва математични и не-аритметични стъпки и следва добре дефиниран концептуален модел, който се поддава на описание, например алгоритъм.
Термините изчислим, разрешим, решим и рекурсивен в контекста на решаването на математическа задача до голяма степен са синоними и говорят за наличието на алгоритъм за решаване[3]. Тюринговата дефиниция за изчислимост по същество е същата: операция, която може да се осъществи от машина[4]
Съществуват обширни научни изследвания относно това кои математически задачи са изчислими и кои не. Изчислимите задачи са класифицирани в класове с различна сложност (на английски: Complexity class). Тези класификации са забележителни със своята яснота, елегантност и точност[3].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.