|
Тема |
Re: Изчислимост -- оопппс [re: Zzz] |
|
Автор | ззз (Нерегистриран) | |
Публикувано | 26.03.08 17:56 |
|
|
Оопс.. не обърнах внимание на думите <за всяка редица>; имах в предвид всяака числова редица която можем да дафинираме <конструктивно> - за нея може да се построи ламбда израз.
В общия случай не може.
Пример:
-- Може да се напише програма (или ламбда израз) който да изброява и исписва всички твърдения в теория на числата ф1, ф2, ф3, ... Това е сигурно че може.
-- Обаче не може да напишам програма която изпива например такъв ред: <ф1,0>, <Ф2,1>, <ф3, 1>, <ф4,0>,.... т.е. да изписва всяка формула от теория на числада и донея 0 лии 1 ако е вярна иле не. Противоречи на теоремата на Гьодел за непълнотата, според която теория на числата е непълна теоря.
Ние - хората - нямаме констуктивно построение за въпросната редица <Ф1, 0>, ... и заради това и машината на Тюринг не може да го направи, т.е. не знаем как да построим такава машина. А как да можем? Според Гьодел не е възможно някой да сеети и да ни каже как се построява.
ОК?
|
| |
|
|
|