Изчислимост: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
доб |
||
Ред 1:
'''Изчислимост''' (поддаващ се на изчисление) ({{lang-en|computability}}) в [[информатика]]та е атрибут<!-- ???? --> на всеки тип [[изчисление]] ({{lang-en|computation}})<ref>[http://www.merriam-webster.com/dictionary/computation Computation] from the Free Merriam-Webster Dictionary</ref><ref>{{cite web|title=Computation: Definition and Synonyms from Answers.com|url=http://www.answers.com:80/topic/computation|website=Answers.com|accessdate=26 April 2017|archiveurl=https://web.archive.org/web/20090222005439/http://www.answers.com:80/topic/computation|archivedate=22 February 2009}}</ref>, което включва математични и не-аритметични стъпки и следва добре дефиниран концептуален модел, който се поддава на описание, например [[алгоритъм]].
Термините '''изчислим''', '''разрешим''', '''решим''' и '''рекурсивен'''в контекста на [[математическа задача]] до голяма степен са [[синоним]]и и говорят за наличието на алгоритъм за решаване<ref name="SPE">{{Цитат уеб| уеб_адрес=https://plato.stanford.edu/entries/computability/ | заглавие= Computability and Complexity|достъп_дата =15 декември 2017 |фамилно_име=Immerman |първо_име= Neil |дата=2016 |труд= |издател=[[Станфордска философска енциклопедия]] |език=en |цитат= }}</ref> . [[Алън Тюринг|Тюринговата]] дефиниция за изчислимост по същество е същата: операция, която може да се осъществи от машина<ref>{{Цитат периодика| last = Hodges | first = Andrew| year =2008 | title =Алън Тюринг – логическата и физическата основа на разрешимостта (превод на „Alan Turing: the logical and physical basis of computing“), бележка под линия 5| journal = Светът на физиката| issue = 4| pages = 486| url = http://wop.phys.uni-sofia.bg/digital_pdf/wop/4_2008.pdf| format = pdf| accessdate =31 юли 2017 }}</ref>
Съществуват обширни научни изследвания относно това кои математически задачи са изчислими и кои не. Изчислимите задачи са класифицирани в класове с различна сложност ({{lang-en|Complexity class}}). Тези класификации са забележителни със своята яснота, елегантност и точност<ref name="SPE"/>.
== Източници ==
| |||