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



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

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

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

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

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

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

Предпосылки

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

Предположим, что функция 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

Густав Роберт Кирхгоф (нем. Gustav Robert Kirchhoff; 12 марта 1824, Кёнигсберг — 17 октября 1887, Берлин) — один из великих фи...

Рассел, Бертран

News image

Бе ртран А ртур Уи льям Ра ссел (англ. Bertrand Arthur William Russell, 3rd Earl Russell; 18 мая 1872 — 2 ...

Авторизация



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

Единицы измерения количества информации

News image

Единицы измерения информации служат для измерения объёма информации — величины, исчисляемой логарифмически. Это означает, что когда несколько объектов рассматриваются как од...

Ом

News image

Ом (обозначение: Ом, Ω) — единица измерения электрического сопротивления в СИ. Ом равен электрическому сопротивлению проводника, между концами которого возникает на...

Миллиметр ртутного столба

News image

Миллиме тр рту тного столба (мм рт. ст., mm Hg) — внесистемная единица измерения давления, равная 101 325 / 76...

Мегабайт

News image

Название «Мегабайт» распространено, но не соответствует ГОСТ 8.417-2002, где приставка мега - означает умножение на 1 000 000, а не 1 ...

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

Вильсон, Чарлз Томсон Риз

News image

Чарлз Томсон Риз Вильсон (англ. Charles Thomson Rees Wilson; 14 февраля 1869, Гленкорс — 15 ноября 1959, Карлопс, пригород Эдинбурга) — шотландский физик, лауреат Нобелевской пр...

Универсальный конвертер
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

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