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



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

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

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

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

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

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

Предпосылки

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

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

Эрвин Рудольф Йозеф Александр Шрёдингер (нем. Erwin Rudolf Josef Alexander Schrödinger, 12 августа 1887, Вена — 4 января 1961, там же...

Ньютон, Исаак

News image

Сэр Исаа к Нью то н (англ. Sir Isaac Newton, 25 декабря 1642 — 20 марта 1727 по юлианскому календарю, де...

Авторизация



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

Градус Гука

News image

Градус Гука (°H) — историческая единица температуры. Шкала Гука считается самой первой фиксированной температурной шкалой. Прообразом для созданной Гуком шкалы стал по...

Бит в секунду

News image

Бит в секунду, бит/с (англ. bits per second, bps) — базовая единица измерения скорости передачи информации, используемая на физическом уровне се...

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

News image

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

Гигабайт

News image

Гигабайт  (Гбайт, Г, ГБ) — кратная единица измерения количества информации, равная 109 стандартных (8-битным) байтов или 1000 мегабайтам. Неправильность названия Читая нижеизложенный те...

Магазин фурнитуры в москве швейные магазины в москве.
Открыватели:

Крик, Фрэнсис

News image

Фрэнсис Крик (англ. Francis Crick, 8 июня 1916, Нортгемптон — 28 июля 2004, Сан-Диего, Калифорния) — британский молекулярный биолог, врач и нейробиолог. Лауреат Нобелевской премии по...

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

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