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



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

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

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

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

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

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

Предпосылки

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

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

Джордж Буль (англ. George Boole; 2 ноября 1815, Линкольн — 8 декабря 1864, Баллинтемпл, графство Корк, Ирландия) — английский математик и ...

Бройль, Луи де

News image

Луи Виктор Пьер Раймон, 7-й герцог Брольи, более известный как Луи де Бройль (фр. Louis-Victor-Pierre-Raymond, 7ème duc de Broglie, Louis de...

Авторизация



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

Гигабайт

News image

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

Байт

News image

Байт (англ. byte) — единица хранения и обработки цифровой информации. Чаще всего байт считается равным восьми битам, в этом случае он...

Бел

News image

Бел (сокращение: Б) — безразмерная единица измерения отношения (разности уровней) некоторых величин (например, энергетических — мощности и энергии или силовых — ...

Метр в секунду

News image

Метр в секунду (м/с) — единица измерения скорости в СИ. Объект, движущийся со скоростью 1 м/с, преодолевает за секунду один ме...

http://www.goashop.com.ua/ все фото по тегу кепка с прямым козырьком нью йорк. . Officecar продажа и преоборудование офисов на колесах.
Открыватели:

Кинси, Альфред

News image

А льфред Чарлз Ки нси (англ. Alfred Charles Kinsey, 23 июня 1894 — 25 августа 1956) — американский биолог, профессор энтомологии и зоологии, основатель института по...

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

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