Почему язык конечных префиксов числа pi определяется с помощью TM
Существует эффективная вычислительная процедура для печати конечных префиксов из цифр числа pi.Ряд Маклаурина для sin (x) равен x - x ^ 3/3!+ х ^ 5/5!- ... Кроме того, мы знаем, что sin (pi / 2) = 1, поэтому мы можем установить 1 = x - x ^ 3/3!+ х ^ 5/5!- ..., начните где-нибудь близко (например, х = 1,5) и найдите наибольшее значение х, которое увеличилось по сравнению с предшественником.Затем умножьте это на 2 и оставьте первые n цифр, чтобы получить префикс длины n.Например:
f(1.50) < f(1.51) < f(1.52) < f(1.53) < f(1.54) < f(1.55) < f(1.56) < f(1.57)
f(1.59) < f(1.58) < f(1.57)
Это говорит нам о том, что x = 1,57 является ближайшим значением к pi / 2 и либо немного больше, либо немного меньше, чем нам действительно нужно.Мы можем определить, проверив ряд Маклаурина для cos (x): мы видим, что cos (1.57) сходится к положительному числу, поэтому мы знаем, что мы находимся на самом большом числе с n цифрами, которые меньше чем pi / 2.Держите вычисление как минимум на один уровень ниже, чем нужно для возврата цифр числа Пи, и все будет хорошо.
, тогда как неверно говорить, что для любого действительного числа существует ТМ, которое определяетконечные префиксы этого заданного числа
Вот реальное число для вас: действительное число от 0 до 1, десятичное представление которого в качестве n-й цифры установлено в 1, если и только если n-й механизм Тьюринга (определенпутем лексикографического упорядочения кодировки UTM всех ТМ) принимает пустой язык.Это четко определенное действительное число - каждая из его десятичных цифр равна 0 или 1 - и все же, если бы у нас была ТМ, которая могла бы найти любой конечный префикс этого действительного числа, мы могли бы ответить на вопрос «принимает ли эта ТМ пустуюязык?»для любой ТМ:
- , кодирующей ТМ в кодировке UTM
- , перечисляющей все строки в лексикографическом порядке и подсчитывающей, сколько действительных кодировок UTM ТМ мы находим
- остановка вычисления при подсчете ТМ, который мы хотим получить для ответа
- , запрашивая префикс, длина которого равна только что полученному счетчику
- , проверяя последнюю цифру префикса, чтобы увидеть,ТМ принимает пустой язык или нет
Это противоречие, так как невозможно решить, принимает ли ТМ пустой язык или нет.Поэтому наше предположение о том, что мы могли бы вычислить конечные префиксы этого действительного числа, было неверным.
Для любой неразрешимой задачи, связанной с ТМ (теорема Райса и аргументы диагонализации гарантируют, что большинство языков кодировок UTM ТМ), вы получаете уникальныйдействительное число, которое не может быть вычислено.Действительно, вычислимые действительные числа являются счетными, как машины Тьюринга, но в отличие от языков и действительных чисел, которые неисчислимы.