Возможности вычислительных машин и человеческий разум



         

Глава 3. Как работают вычислительные машины - стр. 12


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

Допустим, что телефонная книга записана на ленте того типа, который требуется для рассмотренных нами машин Тьюринга. При этом нужно следить не только за движением ленты, связанным со счетными функциями, но каждую запись придется просмотреть гораздо больше двух раз. Так, в нашем примере для самой первой записи потребовалось бы посмотреть ее, 6242 записи между ней и записью 6244 и саму запись 6244. В классической машине Тьюринга нельзя было бы просто прокрутить часть ленты, разделяющей соответствующие записи, а пришлось бы реально прочесть и интерпретировать каждую запись. Тот же принцип объясняет крайнее раздражение, которое некоторые люди испытывают, когда им говорят, что они упомянуты в большой книге, не снабженной указателем. Им приходится читать всю книгу.

Пример с телефонной книгой свидетельствует не только о том, что наличие адреса увеличивает эффективность поиска, но и показывает, что при некоторых обстоятельствах оно вообще исключает необходимость поиска. Дело в том, что на вопрос, образует ли конкретный абонент с другим абонентом пару указанного типа, ответ можно получить непосредственно, не прибегая к поиску среди не относящихся к этим абонентам данных. Входит ли, например, мистер Аабан в подобную пару? Чтобы выяснить это, обратимся сразу к абоненту с номером 6244. Если четыре последние цифры номера его телефона "0001", то ответ - "да", в противном случае - "нет". Имея в виду сказанное, обратимся снова к наборам из пяти элементов, определяющим некоторую машину Тьюринга Т и являющимся, следовательно, программой для универсальной машины Тьюринга, имитирующей машину Т. Напомним, что в общем виде такой набор из пяти элементов задается как

(текущее состояние, текущий символ, очередное состояние, очередной символ, направление).




Содержание  Назад  Вперед