Машина на Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
м форматиране: 2x нов ред, 49 интервала, тире, число+г. (ползвайки Advisor) |
||
Ред 28:
ст. инс. лента
-- – ----------------
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Изобщо, ако началната поредица съдържа '''k''' единици, машината '''Double''' ще спре след изпълнението на '''2k<sup>2</sup>+k+1''' стъпки (без да броим инструкцията за спиране), на лентата ще има '''2k''' единици и главата ще е над най-лявата единица. Тези свойства на '''Double''' могат да бъдат доказани с използване на математическа индукция.
== Изчислимост и алгоритми ==
През 30-те години на XX век били предложени няколко математически определения на понятието ефективен метод (алгоритъм, формална процедура, изчисляващо устройство, компютър). Било също доказано, че всички такива определения са еквивалентни, т.е. класа задачи, които можем да решим с някоя от предложените схеми (примерно с машини на Тюринг) точно съвпада с класа задачи, решими с всяка друга разумна схема за правене на изчисления (примерно най-мощните съвременни компютри, с допълнителна възможност да им добавяме памет по време на изчислението). Тази еквивалентност, приемана като природен закон за всички възможни схеми за изчисляване се нарича [[тезис на Чърч]] по името на американския логик [[Алонсо Чърч]], който я забелязва най-рано.
Line 66 ⟶ 65:
Пак от тезиса на Чърч следва, че когато създаваме нов алгоритъм не е необходимо да се мъчим да го опишем като машина на Тюринг. Достатъчно е да опишем алгоритъма на кой да е от стандартните езици за програмиране. Тезисът гарантира, че получената програма може да се трансформира в еквивалентна машина на Тюринг.
== Нерешими задачи ==
През 30-те години на XX век бил разрешен и следният важен въпрос: Съществуват ли задачи, които могат да се формулират като задачи за изчисляване, но да няма алгоритъм, който ги решава?
Line 76 ⟶ 74:
Друга формулировка: Има ли машина на Тюринг, която да решава дали описана върху лентата ѝ последователност от символи е дефиниция на алгоритъм, еквивалентен на машината '''Double'''?
Горната задача е нерешима и в по-обща формулировка, известна като теорема на Райс, т.е. няма алгоритъм, който да установява еквивалентност на компютърни програми. Такъв тип нерешимост има важно практическо значение
Още през 1936 г. Тюринг доказва, че няма алгоритъм, който да определя дали дадена програма ще завърши изчислението си или ще зацикли.
Нерешимите задачи имат пряка връзка с основите на математиката и математическата логика. Известната [[теорема на Гьодел за непълнота]], изключително важен резултат за математиката, но и за цялата наука и [[философия]]та, доказана още през 1932
== Източници ==
| |||