Изчислимост: Разлика между версии

от Уикипедия, свободната енциклопедия
Изтрито е съдържание Добавено е съдържание
BotNinja (беседа | приноси)
{{lang-en}} => {{lang|en}}
м {{цитат уеб/книга/периодика}} премахване на език-икона= / lang-icon=
Ред 1: Ред 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 април 2017|archiveurl=https://web.archive.org/web/20090222005439/http://www.answers.com:80/topic/computation|archivedate=22 февруари 2009}}</ref>, което включва математични и не-аритметични стъпки и следва добре дефиниран концептуален модел, който се поддава на описание, например [[алгоритъм]].
'''Изчислимост''' (поддаващ се на изчисление) ({{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 април 2017|archiveurl=https://web.archive.org/web/20090222005439/http://www.answers.com:80/topic/computation|archivedate=22 февруари 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>
Термините '''изчислим''', '''разрешим''', '''решим''' и '''рекурсивен''' в контекста на решаването на [[математическа задача]] до голяма степен са [[синоним]]и и говорят за наличието на алгоритъм за решаване<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"/>.
Съществуват обширни научни изследвания относно това кои математически задачи са изчислими и кои не. Изчислимите задачи са класифицирани в класове с различна сложност ({{lang|en|Complexity class}}). Тези класификации са забележителни със своята яснота, елегантност и точност<ref name="SPE"/>.

Версия от 23:00, 31 март 2019

Изчислимост (поддаващ се на изчисление) (на английски: 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 февруари 2009. Посетен на 26 април 2017.
  3. а б Immerman, Neil. Computability and Complexity // Станфордска философска енциклопедия, 2016. Посетен на 15 декември 2017. (на английски)
  4. Hodges, Andrew. Алън Тюринг – логическата и физическата основа на разрешимостта (превод на „Alan Turing: the logical and physical basis of computing“), бележка под линия 5 (pdf) // Светът на физиката (4). 2008. с. 486. Посетен на 31 юли 2017.