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



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

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

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

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

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

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

Предпосылки

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

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

Огюсте н Луи Коши (фр. Augustin Louis Cauchy; 21 августа 1789, Париж — 23 мая 1857, Со (О-де-Сен)) — ...

Виноградов, Александр Павлович

News image

Александр Павлович Виноградов (9 (21) августа 1895, Романово-Борисоглебский уезд Ярославской губернии — 16 ноября 1975, Москва), советский геохимик, организатор и ди...

Авторизация



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

Градус Рёмера

News image

Градус Рёмера (°Rø) — неиспользуемая ныне единица температуры. Температурная шкала Рёмера была создана в 1701 году датским астрономом Оле Кристенсеном Рёмером. Он...

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

News image

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

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

News image

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

Килограмм

News image

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

http://promorechi.com.ua брендированные карандаши киев: магазин карандаш.
Открыватели:

Фибоначчи

News image

Леона рдо Пиза нский (лат. Leonardo Pisano, Пиза, около 1170 — около 1250) — первый крупный математик средневековой Европы. Более известен под прозвищем своего отца Гиль...

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

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