Тјурингов доказ
Тјурингов доказ је доказ Алана Тјуринга, први пут објављен у новембру 1936.[1] под насловом „О израчунљивим бројевима, са применом на Ентсцхеидунгспроблем“. Био је то други доказ (после Черчеве теореме) негације Хилбертовог Ентсцхеидунгспроблем; то јест, претпоставке да се на нека чисто математичка да-не питања никада не може одговорити рачунањем; технички гледано, да су неки проблеми одлучивања „неодлучиви” у смислу да не постоји јединствени алгоритам који непогрешиво даје тачан „да” или „не” одговор на сваку инстанцу проблема. Тјуринговим сопственим речима: „оно што ћу доказати је сасвим другачије од добро познатих Геделових резултата... Сада ћу показати да не постоји општа метода која говори да ли је дата формула У доказива у К [Принципиа Матхематица]“.[2]
Тјуринг је пратио овај доказ са још два друга. Други и трећи се ослањају на први. Сви се ослањају на његов развој „рачунарских машина“ сличних писаћим машинама које се повињавају једноставном скупу правила и на његов каснији развој „универзалне рачунарске машине“.
Сажетак доказа
уредиУ свом доказу да проблем одлуке може бити без решења, Тјуринг је пошао од два доказа који су требали да доведу до његовог коначног доказа. Његова прва теорема је најрелевантнија за проблем заустављања, друга је релевантнија за Рајсову теорему.
Први доказ: да не постоји „рачунарска машина“ која може одлучити да ли је произвољна „рачунарска машина“ (као што је представљена целим бројем 1, 2, 3, . . .) „без круга“ (тј. наставља да штампа свој број у бинарном облику ад инфинитум): „...немамо општи процес да то урадимо у коначном броју корака“ (стр. 132, ибид.). Тјурингов доказ, иако се чини да користи „дијагонални процес“, у ствари показује да његова машина (названа Х) не може да израчуна сопствени број, а камоли цео дијагонални број (Канторов дијагонални аргумент): „Заблуда у аргументу лежи у претпоставка да је Б [дијагонални број] израчунљив“[3] Доказ не захтева много математике.
Други доказ: Овај је читаоцима можда познатији као Рајсова теорема: „Можемо даље показати да не може постојати машина Е која ће, када је снабдевена С.D [„програмом“] произвољне машине M, одредити да ли ће M икада штампа дати симбол (рецимо 0)”[а]
Трећи доказ: „Одговарајући свакој рачунарској машини M конструишемо формулу Ун(M) и показујемо да, ако постоји општи метод за одређивање да ли је Ун(M) доказиво, онда постоји општи метод за одређивање да ли M икада штампа 0”.[2]
Трећи доказ захтева употребу формалне логике за доказивање прве леме, након чега следи кратак доказ друге речима:
Коначно, у само 64 речи и симбола Тјуринг доказује редуцтио ад абсурдум да „Хилбертов проблем одлуке може имати решење“.[2]
Напомене
уреди- ^ хис италицс, Давис (1965), стр. 134
Референце
уреди- ^ Туринг, Алан Матхисон (12. 11. 1936). „Он цомпутабле нумберс, wитх ан апплицатион то тхе Ентсцхеидунгспроблем” (ПДФ). Процеедингс оф тхе Лондон Матхематицал Социетy. 58: 230—265. С2ЦИД 73712. дои:10.1112/плмс/с2-42.1.230.
- ^ а б в Давис (1965), стр. 145.
- ^ Давис (1965), стр. 132.
- ^ Давис (1965), стр. 147.
- ^ Давис (1965), стр. 148.
Литература
уреди- Давис, Мартин (1965). Тхе Ундецидабле, Басиц Паперс он Ундецидабле Пропоситионс, Унсолвабле Проблемс анд Цомпутабле Фунцтионс. Неw Yорк: Равен Пресс. Тхе тwо паперс оф Пост референцед абове аре инцлудед ин тхис волуме. Отхер паперс инцлуде тхосе бy Гöдел, Цхурцх, Россер, анд Клеене.
- Давис, Мартин (2004). Тхе Ундецидабле: Басиц Паперс он Ундецидабле Пропоситионс, Унсолвабле Проблемс анд Цомпутабле Фунцтионс. Довер. ИСБН 9780486432281.
- Франзéн, Торкел (2005). Гöдел'с Тхеорем: Ан Инцомплете Гуиде то итс Усе анд Абусе. А К Петерс.
- Ходгес, Андреw (1983). Алан Туринг: Тхе Енигма. Неw Yорк: Симон анд Сцхустер. Цф. Цхаптер "Тхе Спирит оф Трутх" фор а хисторy леадинг то, анд а дисцуссион оф, хис прооф.
- Реицхенбацх, Ханс (1947). Елементс оф Сyмболиц Логиц. Неw Yорк: Довер Публицатионс, Инц.
- Туринг, А.M. (1937). „Он Цомпутабле Нумберс, wитх ан Апплицатион то тхе Ентсцхеидунгспроблем”. Процеедингс оф тхе Лондон Матхематицал Социетy. 2. 42 (1): 230—65. С2ЦИД 73712. дои:10.1112/плмс/с2-42.1.230.
- Туринг, А.M. (1938). „Он Цомпутабле Нумберс, wитх ан Апплицатион то тхе Ентсцхеидунгспроблем. А Цоррецтион”. Процеедингс оф тхе Лондон Матхематицал Социетy. 2. 43 (6): 544—6. дои:10.1112/плмс/с2-43.6.544. Тхис ис тхе епоцхал папер wхере Туринг дефинес Туринг мацхинес, схоwс тхат тхе Ентсцхеидунгспроблем ис унсолвабле.