|
Тема |
Re: Изчислимост -- оопппс [re: Numberous] |
|
Автор | zzz (Нерегистриран) | |
Публикувано | 28.03.08 20:55 |
|
|
Разбира се, десетичните знаци в числото ПИ и sqrt(2) са безкрайно количество, и няма как машината да ги изпише понеже ще и трябва <безкрайно време> т.е. ако я пуснем, тя вечно ще изписва знаци и никога няма да спре да изписва поредния знак.
Като се казва <изчислимо> се има в пред вид, че машинта на Тюринг е в състояние да ги изписва. Ако поискаме от нея да ни изпише 1,000,000,000-тия знак, тя може да го изпише, ако ще и да работи 100 години за целта. Въпроса е принципен. А практическата стойност е че винаги можем да пресметнем ПИ със всяка точност дето желаем. Това ни е достатъчно.
П.С.
-- Под <редица> се разбира съвкупност от обект, индексирани чрез натурални числа. Отбелязвам това, понеже в топологията се говори за съвкупност от обекти индексирани чрез произволно множество (например филтър на Фреше или насочено множество), което не е редица - тези индексни множества могат да са с по-голяма мощност от натуралните числа. Тук теория на рекурсията не се прилага - машината на Тюринг работи само с натурални числа.
-- Реалните числа някаде се дефинират като множеството от всички равномерно сходящи редици (редици на Коши) от рационални числа. Машината на Тюринг може да борави с рационални числа, понеже те са двойка <числител, знаменател> и лесно се кодират с цели числа. Тези редици за които имаме <конструктивно> построение могат да се изписват от машината на Тюринг, или ко щеш да построим <ламбда-израз> за тях. После може формално да си мислиш че ПИ е еквивалентно на машината или ламбда-израза който е в състояние да генерира цифрите му. Това е напълно легално, и даже интуиционистите признават за съществуващи само тези реални числа, за които можем да построим машина на Тюринг.
|
| |
|
|
|