Алън Тюринг: Разлика между версии

Не само неговата [[ексцентричност]], но и брилянтните му математически способности го отличават от другите. През [[1936]] г. Тюринг публикува известната си статия „Разрешими числа и приложение към Entscheidungsproblem“ <ref>{{Цитат периодика| last = Hodges | first = Andrew| year =2008 | title =Алън Тюринг – логическата и физическата основа на разрешимостта (превод на „Alan Turing: the logical and physical basis of computing“)| journal = Светът на физиката| issue = 4| pages = 486| url = http://wop.phys.uni-sofia.bg/digital_pdf/wop/4_2008.pdf| format = pdf| accessdate =31 юли 2017 }}</ref> („On Computable Numbers, with an Application to the ''Entscheidungsproblem''“{{hrf|Turing|19371936|230 – 265}}{{hrf|Turing|1938|544 – 546}}). Той преформулира [[теорема на Гьодел за непълнота|теоремата]] на [[Курт Гьодел]] от [[1931]] г., като замества универсалния формален език на Гьодел, основан на аритметиката, с просто абстрактно изчислително устройство (нарича го „машина“), което може да извършва действия с произволни числа. Тази „машина“, която съдържа контролен блок, може да извършва няколко основни действия: [[четене]], [[писане]] или изтриване на [[символ]]и върху някаква среда, която той нарича лента (а днес бихме нарекли [[компютърна памет]]) и избутване или пренавиване на лентата. Тюринг доказва, че подобна машина е в състояние да извърши произволни математически изчисления, ако те бъдат представени като [[алгоритъм]] и формулира първите алгоритмично нерешими задачи, като отбелязва връзката им с теоремата на Гьодел. Тази [[машина на Тюринг]] по-късно е използвана като модел за разработването на първите [[компютър|компютри]] и продължава да е основен обект на изучаване в теорията на алгоритмите.

* {{Cite journal | last = Turing | first = A. M | year = 19371936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | origyear = 1936 | journal = Proceedings of the London Mathematical Society | series = 2 | volume = 42 | pages = 230 – 265 | doi= 10.1112/plms/s2-42.1.230 | url = http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf | lang = en}}