Kniga-Online.club
» » » » Питер Эткинз - Десять великих идей науки. Как устроен наш мир.

Питер Эткинз - Десять великих идей науки. Как устроен наш мир.

Читать бесплатно Питер Эткинз - Десять великих идей науки. Как устроен наш мир.. Жанр: Математика издательство неизвестно, год 2004. Так же читаем полные версии (весь текст) онлайн без регистрации и SMS на сайте kniga-online.club или прочесть краткое содержание, предисловие (аннотацию), описание и ознакомиться с отзывами (комментариями) о произведении.
Перейти на страницу:

Машина Тьюринга является прибором, который претендует на имитацию действий человека, производящего некоторого рода алгоритмическое вычисление, то есть вычисление, выполняемое с помощью серии последовательных правил, и в котором мы теперь узнаем представление цифрового компьютера. К первой реализации программируемого цифрового электронного компьютера Тьюринга привела, конечно, его работа со взламыванием кодов во время Второй мировой войны на Блетчли-парк, на севере Лондона, а позже в Манчестере. Благодаря успехам во взламывании кодов, на счету Тьюринга оказалось приписываемое ему уменьшение продолжительности войны на месяцы, если не на годы, и, определенно, спасение многих тысяч жизней. К позору для Англии середины двадцатого столетия, Тьюринг, преследуемый законами и нравами общества того времени (он был гомосексуалистом), рано закончил свою жизнь.

Тьюринг искал путь для извлечения сущности того способа, которым человек производит вычисления, а затем исследовал ограничения этого процесса, пытаясь выяснить, возможен ли вопрос, ответ на который, как бы долго ни работал человек, не будет получен? Вариант процедуры, предложенный Тьюрингом, был заключен в капсулу прибора, состоящего из бесконечно длинной ленты бумаги (в подражание бесконечному источнику бумаги и карандашей, которым может располагать человек-вычислитель при выполнении расчетов, делая записи промежуточных вычислений и затем записывая окончательный ответ) и считывающей и пишущей головки, которую можно запрограммировать так, чтобы она реагировала по определенным правилам на то, что записано в ячейке, проходящей мимо нее в данный момент (рис. 10.10). Эти правила можно было видоизменять и направлять на читающую головку с бумажной ленты.

Рис. 10.10. Версия машины Тьюринга. Машина состоит из бесконечно длинной ленты бумаги, разделенной на ячейки, в которых могут быть записаны символы (обычно, 0 или 1), и механизма, который может считывать эти символы, реагируя на считываемое в соответствии со своим внутренним состоянием в данный момент, меняя символы, если это требуется, и переходя к соседним ячейкам в соответствующем направлении. В этом представлении внутреннее состояние обозначается световым сигналом на одной из сторон считывающей головки. Правая диаграмма показывает возможный отклик: машина находится во внутреннем состоянии, обозначенном световым сигналом, и считывает 1; в результате она заменяет 1 на 0, меняет свое внутреннее состояние и сдвигает ленту на один шаг вправо.

Предположим, что ячейки бумажной ленты могут содержать либо 0, либо 1, а головка, в зависимости от своего внутреннего состояния, может считывать ячейку, записывать в ячейку и передвигать ленту на одну ячейку вправо или влево. Конкретная машина Тьюринга будет выполнять серию операций в зависимости от того, что она обнаружит на ленте, и в соответствии со способом реагирования, на который настроена ее головка. Например, если она обнаруживает на ленте 1, когда сама находится в состоянии «1», она может заменить на ленте 1 на 0, поменять свое внутреннее состояние на «2» и сдвинуть ленту на один шаг вправо. В новой ячейке может оказаться 0. Когда головка находится в состоянии «2» и считывает 0, она, возможно, запрограммирована на сдвиг ленты на один шаг влево, а если она считывает 1, то меняет 1 на 0 и сдвигает ленту на один шаг вправо. Если реакции головки искусно запрограммированы, машину можно использовать для выполнения даже самых сложных вычислений. Реальное конструирование такой головки и ее реакций может быть весьма сложной процедурой, а вычисления могут быть очень медленными, но здесь нас интересует лишь принцип вычислений, а не их эффективность.

Каждая из машин Тьюринга представляет собой специальное устройство из ленты и считывающей головки, определенным образом запрограммированной. Давайте предположим, что мы можем пронумеровать все возможные машины Тьюринга, так что у нас есть склад с ящиками, помеченными знаками t1, t2, и так далее. Если одна из этих машин принимает определенное число и останавливается, мы обнаружим определенное число на выходе. Например, если машина t10 принимает число 3, это может означать 42 на выходе и конец вычислений. Чтобы зарегистрировать этот результат, запишем t10(3) = 42. Однако может существовать комбинация машины и значения числа, для которой вычисления никогда не закончатся, например, если машина t22 принимает число 17. Чтобы зарегистрировать этот результат, запишем t22(17) = □. Перед Тьюрингом стояла задача узнать, существует ли способ проверки всех возможных машин и принимаемых ими значений чисел и принятия на основе этой проверки решения, будут ли вычисления когда-либо закончены.

Чтобы выполнить эту программу, предположим, что существует универсальная машина Тьюринга, которая является такой машиной Тьюринга, которую можно запрограммировать для имитации любой индивидуальной машины Тьюринга. У этой машины входная лента имеет две секции, одна для программы, а другая для данных. Программная часть может состоять из строки чисел, которые инструктируют головку, как реагировать на то, что она обнаруживает на ленте. Например, код 001 может означать:

001: если вы обнаруживаете на ленте 1 и находитесь в состоянии 1, замените 1 на 0, смените ваше внутреннее состояние на состояние 2 и передвиньтесь на один шаг вправо.

Подобным же образом, код 010 может означать:

010: если вы обнаруживаете на ленте 0 и находитесь в состоянии 2, передвиньтесь на один шаг влево; а если вы считываете 1, то замените 1 на 0 и передвиньтесь на один шаг вправо.

Программная часть ленты может выглядеть как …001010…, если эти две инструкции надо выполнить последовательно. Мы будем называть универсальную машину Тьюринга tu. Заметим, что, в то время как индивидуальная машина Тьюринга считывает только данные, универсальная машина сначала считывает программу, чтобы подготовить себя, а затем уж считывает данные. Так, если мы хотим, чтобы она имитировала t10, мы считываем программу 10, то есть множество инструкций, настраивающих машину на работу в режиме t10, а затем скармливаем ей данные. Если данные состоят из числа 3, мы будем ожидать от этого совместного процесса ответ 42 и запишем tu(10,3) = 42, где первое число в скобках является номером машины Тьюринга, которую мы хотели имитировать, а второе число представляет данные.

Предположим теперь, что существует машина Тьюринга, которая может взять программу любой другой машины Тьюринга, например t23, и любое множество данных, и решить, остановится или нет эта комбинация, чтобы напечатать ответ. Мы назовем эту особую машину Тьюринга th (h здесь от английского глагола «halt» — останавливаться). Если th получает остановку для частной комбинации программы и данных, например t23 и 3, она напечатает 1 и остановится; если она определяет, что комбинация не приводит к остановке, например t22 и 17, th напечатает 0 и остановится. Успех Тьюринга выразился в доказательстве того, что th не включена в список всех возможных машин Тьюринга и поэтому не существует. Чтобы проделать это, он использовал аргументы, очень похожие на «диагональные» аргументы, которыми пользовался Кантор для доказательства того, что иррациональные числа несчетны. Вы можете свободно перейти к следующему подразделу, если хотите пропустить вывод этого результата.

Эти аргументы таковы. Предположим, что мы задаем входные данные 0, 1, 2, … и машины Тьюринга t0, t1, t2, … и составляем таблицу, верхним левым фрагментом которой является следующая:

Вход 0 1 2 3 Номер матрицы 0 □ □ □ □ 1 3 □ 4 1 2 1 1 1 1 3 0 1 □ 2

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

Перейти на страницу:

Питер Эткинз читать все книги автора по порядку

Питер Эткинз - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки kniga-online.club.


Десять великих идей науки. Как устроен наш мир. отзывы

Отзывы читателей о книге Десять великих идей науки. Как устроен наш мир., автор: Питер Эткинз. Читайте комментарии и мнения людей о произведении.


Уважаемые читатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.

  • 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
  • 2. Просьба отказаться от оскорблений, угроз и запугиваний.
  • 3. Просьба отказаться от нецензурной лексики.
  • 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.

Надеемся на Ваше понимание и благоразумие. С уважением, администратор kniga-online.


Прокомментировать
Подтвердите что вы не робот:*
Подтвердите что вы не робот:*