Изчислимост

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Изчислимост (поддаващ се на изчисление) (на английски: computability) в информатиката е атрибут на всеки тип изчисление (на английски: computation)[1][2], което включва математични и не-аритметични стъпки и следва добре дефиниран концептуален модел, който се поддава на описание, например алгоритъм.

Термините изчислим, разрешим, решим и рекурсивен в контекста на решаването на математическа задача до голяма степен са синоними и говорят за наличието на алгоритъм за решаване[3] . Тюринговата дефиниция за изчислимост по същество е същата: операция, която може да се осъществи от машина[4]

Съществуват обширни научни изследвания относно това кои математически задачи са изчислими и кои не. Изчислимите задачи са класифицирани в класове с различна сложност (на английски: Complexity class). Тези класификации са забележителни със своята яснота, елегантност и точност[3].

Източници[редактиране | редактиране на кода]

  1. Computation from the Free Merriam-Webster Dictionary
  2. Computation: Definition and Synonyms from Answers.com. // Архив на оригинала от 22 February 2009. Посетен на 26 April 2017.
  3. а б ((en)) Immerman, Neil. Computability and Complexity. // Станфордска философска енциклопедия, 2016. Посетен на 15 декември 2017.
  4. Hodges, Andrew. Алън Тюринг – логическата и физическата основа на разрешимостта (превод на „Alan Turing: the logical and physical basis of computing“), бележка под линия 5. // Светът на физиката (4). 2008. с. 486.