|
Здравей Nedev, въпроса който те вълнува е малко сложен за мен, пък и нямам знание прочетено от другаде, та мога само да спекулирам по въпроса.
Значи както знаеш, аксиомата за избора е <неконструктивна>, в смисил че твърди съществуването на някакви функции за избор, но изобщо не ни подсеща как да ги построим. От тук нататък няма какво да говорим за машината на Тюринг, понеже самото понятие <конструктивно> се определя от някои автори като еквивалентно на факта че може да се построи машина на Тюринг, която да свърши работата.
Все пак, има и така наречения "изброим вариант на Аксиомата за Избора", където се твърди пак същото, но приложено само за изброими фамилии от множества (самите множества не са длъжни да са изброими). Този "изброим" вариант на Аксиомата за Избора е доказуем от теория на множествата, ... например следствие е от аксиомите на ZF.
Това че изброимия вариант на Аксиомата на Избора е следствие на ZF, никак не означава че автоматично получаваме констрикция на машина, която да ни реализира функциите на избор. Както се доказва в теория на рекурсията, има неизчислими целочислени функции от една променлива. Съответно има подмножества на натуралните числа, които са примитивно-рекурсивни, рекурсивни, полу-рекурсивни (частично преброими), .. и такива които не са полу-рекурсивни. Т.е. има под-множества на натуралните числа, които машината на Тюринг не е в състояние да ни разпечата елементите им, а какво остава да питаме за функция дефинирана върху тях?
---
Това за случайните числа е много интересно.
Знаем, че в езиците за програмиране има генератори за псевдо-случайни числа. Значи с право можем да си мислим за такава машина на Тюринг, или компютърна програма:
Да дефинираме списъка R = {Н1, Н2, ... } от реaлни числа, като множество от двойки Нj = <Еj, <нj1, нj2, нj3, ...>>, където <нj1, нj2, нj3, ...> е редица от десетични цифри. Йнтерпретираме Нj като реалното число "0 . нj1 нj2 нj3... * 10 ^ Ej", т.е. <нj1, нj2, нj3, ...> е мантисата, а Ej експонентата на реално число.
__АЛГОРИТЪМ__
(1) Инициализираме списъка R от реaлни числа празен.
(2) Генерираме произволно случайно цяло число Е за експонента и добавяме нов елемент в списъка R за тази експонента с празна мантиса.
(3) За всеки елемент от R генерирам случайно число 0 <= Н <= 9, и го добавяме като пореден знак в мантисата.
(4) премини към точка (2).
Горния алгоритъм, и съответната машина на Тюрунг ще работи вечно. Списъка от генерирани реални числа вечно ще нараства, но числота във всеки краен момент ще е рационални, понеже ще е скрайна мантиса. Ако си помислим че тази машина работи вечно, можем да си мислим че исписва някакви реални числа ... току виж в списъка се окаже е ПИ, но няма никаква гаранция.
При всички случаи тази машина ще генерира изброим бром реални числа; а както знаем, реалните числа са неизброимо много. Някои от генерираните числа могат да са рационални, други ирационални, трети рансцедентни. Нямаме представа.. зависи какво ще излезе от генератора за случайни числа.
---
Изброим брой такива машини можем да построим.
Правим супер машина на Тюринг която на всяка стъпка стартира нова машина от горния тип (паралелен процес) като инициализира генератора различно. После джитка по една стъпка на всяка от горните машини, и зацикля да създаде новата машина.
Всеки ще се досети, че такава супер машина на тюринг е построима. За жалост, изброимо обединение на изброими множества си остава изброимо, и пак няма да генерираме всички реални числа.
|
Re: Изчислимост -- оопппс [re: Nedev]
