Эта странная математика. На краю бесконечности и за ним - [28]

Шрифт
Интервал

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

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

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

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

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

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

По оригинальному описанию Тьюринга был даже сконструирован целый ряд реальных машин – в основном в качестве экспериментов по проектированию или для демонстрации работы простейших вычислительных устройств. Несколько машин было построено из деталей LEGO, в том числе одна – из конструктора LEGO Mindstorms NXT для создания программируемого робота. А вот рабочая модель, созданная изобретателем из штата Висконсин Майком Дэйви, напротив, “воплощает в себе классические эстетичность и функциональность описанной Тьюрингом машины” и сейчас находится в постоянной экспозиции Музея истории компьютеров в городе Маунтин-Вью (штат Калифорния).


Модель машины Тьюринга, построенная Майком Дэйви в соответствии с оригинальной идеей Алана Тьюринга.


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

Продолжить чтение
Рекомендуем почитать
На траверзе — Дакар

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

Историческое образование, наука и историки сибирской периферии в годы сталинизма

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

Интеллигенция в поисках идентичности. Достоевский – Толстой

Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.

Князь Евгений Николаевич Трубецкой – философ, богослов, христианин

Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.

Технологии против Человека. Как мы будем жить, любить и думать в следующие 50 лет?

Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.

Лес. Как устроена лесная экосистема

Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.

Книга Бытия. Общая история происхождения

В “Книге Бытия” Гвидо Тонелли, известный итальянский физик, стоявший у истоков открытия знаменитого бозона Хиггса, описывает историю происхождения Вселенной и эволюцию жизни на Земле с точки зрения фундаментальной физики. Эта книга – одна из наиболее емких, внятных и убедительных попыток ответить на вечный вопрос человечества: “Что же на самом деле произошло в те первые мгновения?” Уместив 13,8 миллиарда лет в библейские “семь дней сотворения мира”, Тонелли увлекает читателя в стремительное путешествие по истории космоса – от Большого взрыва и рождения Вселенной до появления на Земле жизни, человеческого языка и способности человека видеть, понимать и описывать мир вокруг себя.

Невозможность второго рода. Невероятные поиски новой формы вещества

В этой книге увлекательно и доступно от первого лица рассказывается история потрясающего научного открытия. Физик-теоретик Пол Стейнхардт, профессор Принстонского университета, автор важных космологических теорий о ранней Вселенной, в чью честь Международная минералогическая ассоциация в 2014 году назвала новый минерал “стейнхардтитом”, описывает, как была найдена новая форма вещества – квазикристаллы, с конфигурацией атомов, запрещенной законами классической кристаллографии. Это захватывающая история о зарождении нового научного направления, о “невозможности”, которая оказалась возможной, о подлинной страсти и отчаянной храбрости в науке. В формате PDF A4 сохранен издательский макет.

Парадокс добродетели

Ричард Рэнгем, приматолог и антрополог, специалист в области эволюции приматов, профессор Гарвардского университета, подробно и доступно разбирает научную дискуссию по важнейшим вопросам: почему людям, представителям единого биологического вида, свойственны одновременно и удивительная доброта, и немыслимая жестокость; как эти качества, порой выходящие далеко за пределы здравого смысла, появились и закрепились в ходе эволюционной истории человечества; откуда у нас нравственные чувства, понятия о добре и зле; и главное – обречены ли мы своим эволюционным парадоксом на вечную угрозу насилия. В формате PDF A4 сохранен издательский макет книги.