Кіріспе

Кездейсоқ компьютерлік бағдарламаның тоқтату ықтималдығы

Компьютер ғылымдарының алгоритмдік ақпарат теориясының тармағында, Шайтин тұрақтысы (Шайтин омега саны) немесе тоқтату ықтималдығы – бұл нақты сан, ол шартты түрде айтқанда, кездейсоқ құрастырылған бағдарламаның тоқтатылу ықтималдығын көрсетеді. Бұл сандар Грегори Шайтин ұсынған құрылым арқылы қалыптасады. Бағдарламаларды кодтау әдістерінің әрқайсысы үшін (әмбебап, төменде қараңыз) шексіз көп тоқтату ықтималдықтары болғанымен, оларды бір ғана бар сияқты қарастырып, Ω әрпімен белгілеу жиі қолданылады. Ω қолданылатын бағдарламалық кодтауға тәуелді болғандықтан, нақты кодтауға сілтеме жасамағанда, оны кейде Шайтин құрылымы деп атайды. Әрбір тоқтату ықтималдығы – қалыпты және трансцендентті нақты сан, оны есептеу мүмкін емес, яғни оның цифрларын есептеуге арналған алгоритм жоқ. Әрбір тоқтату ықтималдығы Мартин Лёф кездейсоқтығын көрсетеді, яғни оның цифрларын сенімді түрде болжауға қабілетті алгоритм де жоқ.

Өмірбаян

Тоқтату ықтималдығының анықтамасы префикссіз әмбебап есептелетін функцияның болуына негізделген. Мұндай функция, интуитивті түрде, ешқандай жарамды бағдарлама басқа жарамды бағдарламаның тура кеңейтілуі ретінде алынбауы қасиетіне ие бағдарламалау тілін білдіреді. F функциясын бір аргумент – шекті бинарлық тізбек қабылдап, мүмкін бір бинарлық тізбекті шығыс ретінде қайтаратын ішінара функция деп есептейік. F функциясы есептелетін болып саналады, егер оны есептейтін Тьюринг машинасы болса, яғни кез келген шекті бинарлық x және y тізбектері үшін F(x) = y болса және тек қана Тьюринг машинасы x кірісімен берілгенде y лентасында тоқтаса ғана. F функциясы әмбебап деп аталады, егер келесі қасиет орындалса: әрбір бір айнымалыдағы есептелетін f функциясы үшін, барлық x үшін F(wx) = f(x) болатын w тізбегі бар; мұнда wx – w және x тізбектерінің біріктірілуін білдіреді. Бұл F функциясы бір айнымалының кез келген есептелетін функциясын симуляциялау үшін қолданылуы мүмкін екенін білдіреді. Формальды түрде, w – есептелетін f функциясының «скрипті», ал F – осы скриптті кірістің префиксі ретінде талдап, содан кейін кірістің қалған бөлігінде орындайтын «интерпретатор». F функциясының домені – оның анықталған барлық p кірістерінің жиыны. әмбебап F үшін мұндай p жалпы жағдайда бағдарламалық бөлік пен дерек бөлігінің біріктірілуі ретінде де, F функциясы үшін бір бағдарлама ретінде де қарастырылуы мүмкін.

F функциясы префикссіз деп аталады, егер оның доменінде p және p′ екі элементі болмаса, онда p′ – p-нің тура кеңейтілуі болып табылады. Бұл былайша да айтуға болады: F функциясының домені – шекті бинарлық тізбектер жиынындағы префикссіз код (жедел код). Префикссіздікті қамтамасыз етудің қарапайым тәсілі – кіріс құралы біттерді біртіндеп оқитын бинарлық ағын болатын машиналарды пайдалану. Ағынның соңы жоқ; кіріс соңы әмбебап машинаның тағы біттерді оқуды тоқтату туралы шешім қабылдауымен анықталады, ал қалған биттер қабылданған тізбектің бөлігі болып саналмайды. Осы абзацтың соңында айтылған бағдарламаның екі түсінігінің арасындағы айырмашылық осы жерде айқын болады: біреуін белгілі бір грамматикамен оңай тануға болады, ал екіншісін тану үшін кез келген есептеу қажет. Кез келген әмбебап есептелетін функцияның домені – есептелетін жиын, бірақ ешқашан есептелетін жиын емес. Домен әрқашан тоқтату мәселесімен теңдес Тьюрингтік.

Тоқтату проблемасымен байланыс

Ω-ның алғашқы N битін білген адам, N-ге дейінгі өлшемдегі барлық бағдарламалар үшін тоқтату мәселесін есептей алады. Тоқтату мәселесін шешуге арналған p бағдарламасы N биттен тұрсын. Доветайлинг әдісімен барлық ұзындықтағы бағдарламалар орындалады, осы алғашқы N биттерге сәйкес келетін жеткілікті ықтималдық жинақталғанша, жеткілікті бағдарламалар тоқтағанға дейін. Егер p бағдарламасы әлі тоқтамаған болса, онда ол ешқашан тоқтамайды, өйткені оның тоқтату ықтималдығына үлесі алғашқы N биттерге әсер етеді. Осылайша, тоқтату мәселесі p үшін шешіледі. Сандар теориясындағы көптеген шешілмеген мәселелер, мысалы Голдбахтың болжамы, арнайы бағдарламалар үшін тоқтату мәселесін шешумен тең (бұл, негізінен, кері мысалдарды іздеу және оны тапқан жағдайда тоқтату), сондықтан Шайтин тұрақтысының жеткілікті битін білу осы мәселелердің жауабын білуді білдіреді. Бірақ тоқтату мәселесі жалпы жағдайда шешілмейтіндіктен, және де Шайтин тұрақтысының алғашқы біттерінен басқаларын есептеу өте ықшам тілде мүмкін емес, бұл қиын мәселелерді тіпті шешілмейтін мәселелерге дейін кемітеді, тоқтату мәселесі үшін оракул машинасы құруға тырысу сияқты.

Есептеуге болмайтындық

Нақты сан есептелуге болады деп аталады, егер n берілгенде, сандағы алғашқы n цифрын қайтаратын алгоритм болса. Бұл нақты санның цифрларын тізімдейтін бағдарламаның болуымен тең. Тоқтату ықтималдығы есептелуге болмайды. Бұл фактіні дәлелдеу, Ω-ның алғашқы n цифры берілгенде, n ұзындығына дейінгі бағдарламалар үшін Тьюрингтің тоқтату мәселесін шешетін алгоритмге негізделген. Тоқтату мәселесі шешілмейтіндіктен, Ω есептелуге болмайды. Алгоритм келесідей жұмыс істейді. Ω-ның алғашқы n цифры және k ≤ n берілген жағдайда, алгоритм F доменін олардың көрсеткен ықтималдығы 2−(k+1) Ω-ның ішінде болатын домен элементтері жеткілікті мөлшерде табылғанша тізімдейді. Осы нүктеден кейін k ұзындығындағы қосымша бағдарлама доменде болуы мүмкін емес, себебі олардың әрқайсысы өлшемге 2−k қосады, бұл мүмкін емес. Осылайша, k ұзындығындағы домендегі жолдар жиыны, осыған дейін тізімделген жолдар жиынымен сәйкес келеді.

Алгоритмдік кездейсоқтық

Нақты сан кездейсоқ болады, егер нақты санды көрсететін екілік тізбек алгоритмдік түрде кездейсоқ тізбек болса. Калуд, Гертлинг, Хуссейнов және Ван рекурсивті санамалы нақты санның алгоритмдік түрде кездейсоқ тізбек болатынын дәлелдеді, оның шарты – ол Чайтиннің Ω саны болуы керек.

Тоқтату ықтималдығы бойынша толық еместік теоремасы

Табиғи сандар үшін әрбір нақты, дәйекті және тиімді түрде ұсынылған аксиоматикалық жүйе, мысалы, Пеано арифметикасы үшін, N тұрақтысы бар, ондағы жүйенің N-ші бітінен кейінгі Ω-ның кез келген біті 1 немесе 0 екені дәлелдене алмайды. N тұрақтысы формальды жүйенің тиімді ұсынылу тәсіліне байланысты және сондықтан аксиоматикалық жүйенің күрделілігін тікелей көрсетпейді. Бұл толық еместік нәтижесі Гёдельдің толық еместік теоремасына ұқсас, себебі ол арифметика үшін ешбір дәйекті формальды теория толық бола алмайтынын көрсетеді.

Супер Омега

Жоғарыда айтылғандай, Грегори Чейтин тұрақтысының алғашқы n биті кездейсоқ немесе қысылмайтын, яғни оларды n O(1) биттен кем тоқтату алгоритмімен есептеу мүмкін емес. Дегенмен, барлық мүмкін бағдарламаларды жүйелі түрде тізімдейтін және іске қосатын, бірақ ешқашан тоқтамайтын қысқа алгоритмді қарастырайық; олардың біреуі тоқтағанда, оның ықтималдығы шығысқа қосылады (бастапқы мәні нөл). Шекті уақыт өткеннен кейін, шығыстың алғашқы n биті енді өзгермейді (осы уақыттың өзі тоқтату бағдарламасымен есептелмейтіні маңызды емес). Демек, шығысы (біраз уақыттан кейін) Ω-ның алғашқы n битіне жақындайтын қысқа тоқтамайтын алгоритм бар. Басқаша айтқанда, Ω-ның саналатын алғашқы n биті өте қысқа алгоритммен шекті түрде есептелетін болғандықтан, жоғары қысылатын болады; олар санау алгоритмдері жиынтығына қатысты кездейсоқ емес. Юрген Шмидхубер (2000) түпнұсқалық шекті есептелетін Ω-ға қарағанда әлдеқайда кездейсоқ болатын шекті есептелетін "Супер Ω" құрастырды, себебі Супер Ω-ны кез келген санаусыз тоқтамайтын алгоритммен мағыналы түрде қысуға болмайды. "Супер Ω" альтернативасы ретінде, префиксі жоқ Универсалды Тьюринг машинасының (UTM) әмбебаптық ықтималдығын қарастыруға болады, атап айтқанда, оның әрбір кірісі (бинарлық тізбек ретінде) кездейсоқ бинарлық тізбекпен префикстелген жағдайда да әмбебап болып қалатын ықтималдығы, тоқтату мәселесінің үшінші итерациясымен (яғни Тьюринг секіру нотациясын пайдалану) оракул бар машинаның тоқтату ықтималдығы ретінде қарастырылуы мүмкін.