Читаем Эта странная математика полностью

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

Простой пример: прибавление к цепочке из n единиц еще одной, или, другими словами, превращение

n в n + 1. Входные данные в этом случае – последовательность единиц и за ней пустая ячейка либо, если n
 = 0, просто пустая ячейка. Головке дается первая команда: перейти к первой непустой ячейке – или, если известно, что на ленте нет вообще никаких данных, начать с любой ячейки – и считать ее содержимое. В случае, если в ячейке стоит 1, дается команда оставить ее как есть и перейти на одну ячейку вправо, не переключаясь в другое состояние; если же ячейка пустая, дается команда записать в ней 1 и остановиться. Дописав к цепочке цифр единицу, головка может, в зависимости от полученной команды, либо остановиться, либо вернуться в исходную позицию – например, для того чтобы начать процесс заново и дописать к цепочке еще одну единицу. Как вариант, после размещения головки над последней в цепочке единицей может быть введено какое-либо иное состояние, после чего головка начнет выполнять новый набор команд.

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

Затем Тьюринг создал в своем воображении особый вид вычислительной машины, известный сегодня под названием “универсальная машина Тьюринга”. Теоретически она была способна выполнять любую программу. Лента ее разделена на две части: на одной закодирована программа, на другой содержатся входные данные. Головка чтения-записи универсальной машины Тьюринга может перемещаться между этими частями и выполнять над входными данными операции в соответствии с командами, записанными в программе. Устройство предельно просто: бесконечно длинная лента, на которой содержится как программа, которую следует выполнить, так и входные и выходные данные, плюс головка чтения-записи. Машина может выполнять всего шесть простых операций: считывание, запись, перемещение влево, вправо, изменение состояния и остановка. Но, несмотря на эту простоту, возможности универсальной машины Тьюринга поражают воображение.

У вас наверняка есть хотя бы один компьютер. Неважно, какая на нем операционная система – какая-нибудь из версий Windows, Mac или Android либо иная, скажем, Linux

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

Изобретение универсальной машины Тьюринга привело к возникновению такого понятия, как эмуляция. Говорят, что один компьютер способен эмулировать некий другой, если он может выполнять программу (называемую эмулятором), которая фактически превращает его в этот другой компьютер. Например, компьютер, работающий под управлением операционной системы Mac OS, может выполнить программу, которая заставит его вести себя так, как если бы на нем была установлена система Windows, – правда, на это требуется много оперативной памяти, а обработка данных происходит медленно. Если подобная эмуляция возможна, два компьютера считаются математически эквивалентными.

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

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

Все книги серии Библиотека фонда «Эволюция»

Происхождение жизни. От туманности до клетки
Происхождение жизни. От туманности до клетки

Поражаясь красоте и многообразию окружающего мира, люди на протяжении веков гадали: как он появился? Каким образом сформировались планеты, на одной из которых зародилась жизнь? Почему земная жизнь основана на углероде и использует четыре типа звеньев в ДНК? Где во Вселенной стоит искать другие формы жизни, и чем они могут отличаться от нас? В этой книге собраны самые свежие ответы науки на эти вопросы. И хотя на переднем крае науки не всегда есть простые пути, автор честно постарался сделать все возможное, чтобы книга была понятна читателям, далеким от биологии. Он логично и четко формулирует свои идеи и с увлечением рассказывает о том, каким образом из космической пыли и метеоритов через горячие источники у подножия вулканов возникла живая клетка, чтобы заселить и преобразить всю планету.

Михаил Александрович Никитин

Научная литература
Ни кошелька, ни жизни. Нетрадиционная медицина под следствием
Ни кошелька, ни жизни. Нетрадиционная медицина под следствием

"Ни кошелька, ни жизни" Саймона Сингха и Эдзарда Эрнста – правдивый, непредвзятый и увлекательный рассказ о нетрадиционной медицине. Основная часть книги посвящена четырем самым популярным ее направлениям – акупунктуре, гомеопатии, хиропрактике и траволечению, а в приложении кратко обсуждаются еще свыше тридцати. Авторы с самого начала разъясняют, что представляет собой научный подход и как с его помощью определяют истину, а затем, опираясь на результаты многочисленных научных исследований, страница за страницей приподнимают завесу тайны, скрывающую неутешительную правду о нетрадиционной медицине. Они разбираются, какие из ее методов действенны и безвредны, а какие бесполезны и опасны. Анализируя, почему во всем мире так широко распространены методы лечения, не доказавшие своей эффективности, они отвечают не только на вездесущий вопрос "Кто виноват?", но и на важнейший вопрос "Что делать?".

Саймон Сингх , Эрдзард Эрнст

Домоводство / Научпоп / Документальное
Введение в поведение. История наук о том, что движет животными и как их правильно понимать
Введение в поведение. История наук о том, что движет животными и как их правильно понимать

На протяжении всей своей истории человек учился понимать других живых существ. А коль скоро они не могут поведать о себе на доступном нам языке, остается один ориентир – их поведение. Книга научного журналиста Бориса Жукова – своего рода карта дорог, которыми человечество пыталось прийти к пониманию этого феномена. Следуя исторической канве, автор рассматривает различные теоретические подходы к изучению поведения, сложные взаимоотношения разных научных направлений между собой и со смежными дисциплинами (физиологией, психологией, теорией эволюции и т. д.), связь представлений о поведении с общенаучными и общемировоззренческими установками той или иной эпохи.Развитие науки представлено не как простое накопление знаний, но как «драма идей», сложный и часто парадоксальный процесс, где конечные выводы порой противоречат исходным постулатам, а замечательные открытия становятся почвой для новых заблуждений.

Борис Борисович Жуков

Зоология / Научная литература

Похожие книги

27 принципов истории. Секреты сторителлинга от «Гамлета» до «Южного парка»
27 принципов истории. Секреты сторителлинга от «Гамлета» до «Южного парка»

Не важно, что вы пишете – роман, сценарий к фильму или сериалу, пьесу, подкаст или комикс, – принципы построения истории едины для всего. И ВСЕГО ИХ 27!Эта книга научит вас создавать историю, у которой есть начало, середина и конец. Которая захватывает и создает напряжение, которая заставляет читателя гадать, что же будет дальше.Вы не найдете здесь никакой теории литературы, академических сложных понятий или профессионального жаргона. Все двадцать семь принципов изложены на простом человеческом языке. Если вы хотите поэтапно, шаг за шагом, узнать, как наилучшим образом рассказать связную. достоверную историю, вы найдете здесь то. что вам нужно. Если вы не приемлете каких-либо рамок и склонны к более свободному полету фантазии, вы можете изучать каждый принцип отдельно и использовать только те. которые покажутся вам наиболее полезными. Главным здесь являетесь только вы сами.В формате PDF A4 сохранен издательский макет книги.

Дэниел Джошуа Рубин

Зарубежная образовательная литература, зарубежная прикладная, научно-популярная литература / Зарубежная прикладная литература / Дом и досуг
Искусство статистики. Как находить ответы в данных
Искусство статистики. Как находить ответы в данных

Статистика играла ключевую роль в научном познании мира на протяжении веков, а в эпоху больших данных базовое понимание этой дисциплины и статистическая грамотность становятся критически важными. Дэвид Шпигельхалтер приглашает вас в не обремененное техническими деталями увлекательное знакомство с теорией и практикой статистики.Эта книга предназначена как для студентов, которые хотят ознакомиться со статистикой, не углубляясь в технические детали, так и для широкого круга читателей, интересующихся статистикой, с которой они сталкиваются на работе и в повседневной жизни. Но даже опытные аналитики найдут в книге интересные примеры и новые знания для своей практики.На русском языке публикуется впервые.

Дэвид Шпигельхалтер

Зарубежная образовательная литература, зарубежная прикладная, научно-популярная литература
Физика повседневности. От мыльных пузырей до квантовых технологий
Физика повседневности. От мыльных пузырей до квантовых технологий

Почему при течении воды в реках возникают меандры? Как заставить бокал запеть? Можно ли построить переговорную трубку между Парижем и Марселем? Какие законы определяют форму капель и пузырьков? Что происходит при приготовлении жаркого? Можно ли попробовать спагетти альденте на вершине Эвереста? А выпить там хороший кофе? На все эти вопросы, как и на многие другие, читатель найдет ответы в этой книге. Каждая страница книги приглашает удивляться, хотя в ней обсуждаются физические явления, лежащие в основе нашей повседневной жизни. В ней не забыты и последние достижения физики: авторы посвящают читателя в тайны квантовой механики и сверхпроводимости, рассказывают о физических основах магнитно-резонансной томографии и о квантовых технологиях. От главы к главе читатель знакомится с неисчислимыми гранями физического мира. Отмеченные Нобелевскими премиями фундаментальные результаты следуют за описаниями, казалось бы, незначительных явлений природы, на которых тем не менее и держится все величественное здание физики.

Андрей Варламов , Аттилио Ригамонти , Жак Виллен

Зарубежная образовательная литература, зарубежная прикладная, научно-популярная литература
История астрономии. Великие открытия с древности до Средневековья
История астрономии. Великие открытия с древности до Средневековья

Книга авторитетного британского ученого Джона Дрейера посвящена истории астрономии с древнейших времен до XVII века. Автор прослеживает эволюцию представлений об устройстве Вселенной, начиная с воззрений древних египтян, вавилонян и греков, освещает космологические теории Фалеса, Анаксимандра, Парменида и других греческих натурфилософов, знакомит с учением пифагорейцев и идеями Платона. Дрейер подробно описывает теорию концентрических планетных сфер Евдокса и Калиппа и геоцентрическую систему мироздания Птолемея. Далее автор рассматривает научные воззрения средневековых ученых Запада и Востока, идеи Николая Кузанского, Региомонтана, Кальканьини и других мыслителей эпохи Возрождения и завершает свой исчерпывающий труд изложением теорий Коперника, Тихо Браге и Кеплера.

Джон Дрейер

Зарубежная образовательная литература, зарубежная прикладная, научно-популярная литература / Прочая научная литература / Образование и наука