Уикипедия

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

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
Addbot (беседа | приноси)
145 445 редакции
м Bot: Migrating 50 interwiki links, now provided by Wikidata on d:q163310 (translate me)
м +картинка
Ред 1:
[[File:Maquina.png|thumb|Художествено представяне на машината на Тюринг]]
'''Машина на Тюринг''' е абстрактно изчислително устройство, описано от английския математик [[Алън Тюринг]] през [[1936]] г.
 
Тюринг използва машинататази абстракция, за да даде първото точно определение на понятието [[алгоритъм]] (наричано още механична, формална или ефективна процедура). Машината се използва при доказването на основни резултати в [[компютърни науки|компютърните науки]], най-вече в областите [[изчислимост]] и [[сложност на алгоритмите]], както и в [[математическата логика]].
 
== Определение ==
Line 56 ⟶ 57:
== Изчислимост и алгоритми ==
 
През 30-те години на XX век били предложени няколко математически определения на понятието ефективен метод (алгоритъм, формална процедура, изчисляващо устройство, компютър). Било също доказано, че всички такива определения са еквивалентни, т.е. класа задачи, които можем да решим с някоя от предложените схеми (примерно с машини на Тюринг) точно съвпада с класа задачи, решими с всяка друга разумна схема за правене на изчисления (примерно най-мощните съвременни компютри, с допълнителна възможност да им добавяме памет по време на изчислението). Тази еквивалентност, приемана като природен закон за всички възможни схеми за изчисляване се нарича [[тезис на Чърч]] по името на американскиятамериканския логик [[Алонсо Чърч]], който я забелязва най-рано.
 
Тезисът на Чърч позволява да се дефинира (определи) понятието алгоритъм така:
Line 64 ⟶ 65:
Машината '''Double''', която описахме по-горе представя универсален алгоритъм за удвояване на число, независимо колко голямо е то. За решаването на една задача може да има различни алгоритми. Числото в нашия примерен алгоритъм беше представено в линейно кодиране и удвояването му е доста бавно. Можем да направим друга, по-ефективна машина на Тюринг за удвояване, която да ползва азбука от 3 букви (празен символ ' ', '0' и '1'), числото на лентата да е записано в двоичен код, при което удвояването ще се сведе до изписването на '0' в първата празна клетка отдясно на числото.
 
Пак от тезисъттезиса на Чърч следва, че не е необходимо когато създаваме нов алгоритъм не е необходимо да се мъчим да го опишем като машина на Тюринг. Достатъчно е да опишем алгоритъма на кой да е от стандартните езици за програмиране. Тезисът гарантира, че получената програма може да се трансформира в еквивалентна машина на Тюринг.
 
== Нерешими задачи ==
 
През 30-те години на XX век бил разрешен и следният важен въпрос: Съществуват ли задачи, които могат да се изразятформулират като задачи за изчисляване, но да няма алгоритъм, който да ги решава?
 
Оказва се, че има много такива задачи. Ето една нерешима задача:
Line 78 ⟶ 79:
Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение — ''не можем да създадем автоматизирани средства за проверка на коректността на компютърните програми''.
 
Още през 1936 г. Тюринг доказва, че няма алгоритъм, който да определя дали дадена програма ще завърши изчислението си или ще се зацикли.
 
Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната [[теорема на Гьодел за непълнота]], изключително важен резултат за математиката и цялата наука и [[философия]], доказана още през 1932 г. конструира специално неразрешимо твърдение за всяка достатъчно богата формална математическа теория. Това Гьоделево твърдение, което нито може да се докаже, нито да се опровергае съсс формални математически методи, по същество е еквивалентно на алгоритмично нерешима задача.
 
== Вижте също ==
Взето от „https://bg.wikipedia.org/wiki/Машина_на_Тюринг“.