Главная Математические константы Константа Хайтина



Константа Хайтина

Наука и константы - Математические константы

константа хайтина

В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — действительное число, которое неформально называют вероятностью того, что произвольно выбранная программа остановится. Построением этих чисел мы обязаны Грегори Хайтину.

Хотя существует бесконечное множество вероятностей остановки, обычно используют букву Ω для обозначения их всех, как если бы существовало только одно такое число. Так как численное значение Ω зависит от используемого языка программирования, то если не ссылаются на какой-то определенный язык, её часто называют построением Хайтина, а не константой Хайтина.

Всякое Ω является нормальным трансцендентным числом, которое определимо, но невычислимо (то, что некое определимое число невычислимо требует обоснования!), что означает отсутствие алгоритма, который перечислял бы его цифры.

Предпосылки

Определение вероятности остановки основывается на существовании префиксных универсальных вычислимых функций. Такие функции, если наглядно, представляют собой язык программирования с тем свойством, что ни одна верная программа не может быть получена как соответствующее расширение другой верной программы.

Предположим, что функция F зависит от двух аргументов, каждый из которых является конечной двоичной строкой, и возвращает одну двоичную строку на выходе. Функция F называется вычислимой, если существует машина Тьюринга, которая её вычисляет.

Функция F называется универсальной, если выполняются следующие условия: для каждой вычислимой функции f одной переменной x существует постоянная p, такая что для любого x, F(p,x) = f(x). То есть, F может быть использована для моделирования любой вычислимой функции одной переменной. Нестрого, p представляет «программу» для вычислимой функции f, а F представляет эмулятор, которому на вход поступает программа и он её выполняет. Следует заметить, что для любого фиксированного p функция f(x) = F(p,x) является вычислимой; таким образом, свойство универсальности утверждает, что таким путём могут быть получены все вычислимые функции одной переменной.

Областью определения F является множество всех программ p, таких что хотя бы для одного значения x значение F(p,x) определенно. Функция называется префиксной, если в её области определения не существует двух элементов p, p&prime, таких что p&prime является соответствующем расширением p. Утверждение можно перефразировать следующим образом: область определения есть префиксный код на множестве двоичных строк конечной длины. Областью определения любой универсальной вычислимой функции является перечислимым множеством, но никогда не вычислимым множеством. Эта область определения всегда имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки.

Определение вероятностей остановки

Пусть PF — область определения префиксной универсальной вычислимой функции F. Константа ΩF тогда определяется как

,

где | p | обозначает длину строки p. Эта бесконечная сумма по всем p из области определения F. То требование, что область определения префиксно, совместно с неравенством Крафта, достаточны для сходимости этой суммы к действительному числу от 0 до 1. Если F ясно из контекста, тогда ΩF может быть обозначена просто как Ω, хотя различные префиксные универсальные вычислимые функции приводят к различным значениям Ω.

Применение Ω к доказательству нерешённых проблем теории чисел

Константа Хайтина, в принципе, может быть использована для решения многих выдающихся проблем теории чисел, включая проблему Гольдбаха и гипотезы Римана.[1] Формулировка проблемы Гольдбаха утверждает, что любое четное число является суммой двух простых. Пусть для заданного четного числа компьютерная программа ищет соответствующие простые числа. Если догадка Гольдбаха верна, программа переходит к следующему четному числу и поиск продолжается. Если не существует двух простых чисел, в сумме дающих требуемое четное число, то будет найден контрпример, программа остановится и догадка Гольдбаха будет опровергнута. Пусть длина этой программы N бит. Если имеются неограниченные ресурсы и время, константа Хайтина может быть использована для доказательства догадки Гольдбаха следующим образом. Пусть параллельно запущены все программы длиной N+1 бит или менее. Если такая N-битная программа останавливается, тогда будет доказано, что догадка Гольдбаха неверна. Если же, с другой стороны, достаточное число других программ остановятся, так что ещё одна остановившаяся программа приведет к числу, превышающему константу Хайтина, тогда если программа не остановилась, то она никогда не остановится и доказано. Для того, чтобы применить этот метод нам необходимы лишь первые N бит константы Хайтина.

Та же константа Хайтина может быть использована для доказательства гипотезы Римана и множества других нерешённых проблем математики.

 

Добавить комментарий


Защитный код
Обновить

Учёные первооткрыватели:

Михайлов, Александр Александрович

News image

Алекса ндр Алекса ндрович Миха йлов (16 (26) апреля 1888, Моршанск — 29 сентября 1983, Ленинград) — советский (российский) астроном, чл...

Тесла, Никола

News image

Нико ла Те сла (серб. Никола Тесла; 10 июля 1856, Смиляны, Австро-Венгрия, ныне в Хорватии — 7 января 1943, Нью-Йорк, СШ...

Авторизация



Единицы измерений:

Неделя

News image

Неде ля (калька с греческого греч. άπρακτος — «не-делающий», «не-дельный») — единица времени, большая, чем день, и меньшая месяца. Семидневное ус...

Атмосфера (единица измерения)

News image

Атмосфера — внесистемная единица измерения давления, приблизительно равная атмосферному давлению на поверхности Земли на уровне Мирового океана. Существуют две примерно равные др...

Виргата

News image

Виргата (англ. virgate; yardland; лат. virgata) — единица измерения площади земельных участков в средневековой Англии, равная 1/4 части гайды. Величина ви...

Британская термическая единица

News image

Британская тепловая единица (BTU, англ. British thermal unit) — единица измерения энергии, используемая в США. В настоящее время используется в ос...

Открыватели:

Мензбир, Михаил Александрович

News image

Михаил Александрович Мензбир (1855—1935) — известный русский и советский зоолог и зоогеограф, основатель русской орнитологии, действительный член АН СССР (1929). Профессор (с 1886) и ректор Мо...

Универсальный конвертер
Conversion Type:
Quantity:

converts to:

Construction Unit converter provided by: EcoLog Homes

Интересные факты:

Таблица Менделеева

News image

В конце августа 1875 г. в кабинет акад. Вюрца входит его ученик, молодой французский химик Лекок-де-Буабодран. н долго не решается об...

Эйнштейн и квантовая теория света

News image

Эйнштейн является одним из основателей новой, квантовой теории света и основателем теории относительности. Согласно квантовой теории свет представляет поток своеобразных ча...

Как происходит кристаллизация жидкости

News image

В настоящее время можно считать твердо установленным, что жидкость может затвердевать после ее охлаждения до температуры плавления только при наличии в ...

О звуке

News image

Звук с давних пор считался одним из самых загадочных явлений природы. В самом деле, что порождает звук? Что заставляет его не...

Атом и время

News image

Трудно себе представить более простое и вместе с тем более сложное понятие, чем время. Старая пословица говорит: «нет ничего в ми...

Ньютон и Марат о притяжении лучей света

News image

Что такое свет?— На этот вопрос Ньютон, очень много поработавший над изуче­нием световых явлений, отвечал так: свет — это поток бы...