Изчислимост (поддаващ се на изчисление) () в информатиката е атрибут на всеки тип изчисление ()Computation from the Free Merriam-Webster Dictionary, което включва математични и не-аритметични стъпки и следва добре дефиниран концептуален модел, който се поддава на описание, например алгоритъм.
Термините изчислим, разрешим, решим и рекурсивен в контекста на решаването на математическа задача до голяма степен са синоними и говорят за наличието на алгоритъм за решаване. Тюринговата дефиниция за изчислимост по същество е същата: операция, която може да се осъществи от машина
Съществуват обширни научни изследвания относно това кои математически задачи са изчислими и кои не. Изчислимите задачи са класифицирани в класове с различна сложност (). Тези класификации са забележителни със своята яснота, елегантност и точност.
Източници
Категория:Информатика