|
Тема |
Re: Изчислимост [re: Numberous] |
|
Автор | Zzz (Нерегистриран) | |
Публикувано | 26.03.08 17:30 |
|
|
Разбира се че може. Може да се състави ламбда-израз, да се построи машина на Тюринг, или да се напише компютърна програма, която изброява елементите на редицата.
Нали според така наречения "Тезис на Чърч" който ти спомена на друго място, това което изобщо може да сметне човек (да изброи, калкулира, да изпише..) може да го направи машимата на Тюринг, ламбда-смятането, и т.н. Даже повече -- човек е смъртен и бавно смята. Една машина на Тюринг (или компютър) може да работо 1000 години и да изписва поредния знак от числото ПИ. Самия ред е безкраен и никога няма да спре да се изписва .. но важното е че машината може да достигне до които и да е знак... ако трябва да работи и 2000 години :)
(което не значи, чв няма неразрешими проблеми; в теория на рекурсията се доказват много теореми за не-разрешими проблеми - нито машината на Тщринг нито човек е в състояние да ги реши; например логиката от 1-ви порядък е неразрешима, както показва и теоремата на Гьодел - т.е. има достатъчно силни теории в които има верни твърдения но не-доказуеми).
|
| |
|
|
|