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

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


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


Как уже упоминалось, свое изящное устройство Тьюринг придумал специально для того, чтобы дать ответ на проблему разрешимости, сформулированную Гильбертом, что он и сделал в своей статье 1936 года, озаглавленной “О вычислимых числах применительно к Entscheidungsproblem”. Если ввести в универсальную машину Тьюринга произвольные входные данные, она может либо остановиться, либо продолжать работать бесконечно. Тьюринг задался вопросом: возможно ли определить, остановится она или нет? Можно, конечно, запустить ее на неопределенное время и посмотреть, что произойдет. Но если после долгого ожидания вы решите досрочно прекратить эксперимент, не дождавшись результата, то так и не узнаете, остановилась бы машина сразу после этого этапа, гораздо позже либо продолжала бы работать бесконечно. Разумеется, для конкретных случаев просчитать результат можно, как мы в силах выяснить, остановится ли когда-нибудь простая машина Тьюринга. Однако Тьюринг хотел знать, существует ли общий алгоритм, способный для любых входных данных определить, остановится машина или нет. Эта задача получила название “проблема остановки”, и Тьюринг доказал, что такого алгоритма не существует. Далее, в заключительной части своей статьи, он показал, что отсюда следует вывод о неразрешимости Entscheidungsproblem

. А это значит, что мы можем быть абсолютно уверены: никакая самая совершенная компьютерная программа не сумеет – во всех случаях – определить, завершит ли когда-нибудь свою работу какая-либо иная программа.

За месяц до выхода исторической статьи Тьюринга американский ученый-логик Алонзо Чёрч, его научный руководитель, независимо опубликовал собственную статью, в которой делал тот же вывод, но для доказательства использовал совершенно другой метод – лямбда-исчисление. Так же как и машина Тьюринга, лямбда-исчисление представляет собой универсальную вычислительную модель, но скорее программную, а не аппаратную; она оперирует “комбинаторами” – функциями, которые применяются к другим функциям. И Чёрч, и Тьюринг, пользуясь каждый своим методом, пришли, в сущности, к одному и тому же результату, получившему название “тезис Чёрча – Тьюринга”. Суть его в том, что человек способен высчитать или оценить количественно (такую мелочь, как ограниченность ресурсов, мы при этом в расчет не берем) только то, что вычислимо с помощью машины Тьюринга или равнозначного ей устройства. “Вычислимость” означает, что машина Тьюринга, если подать ей на вход программу (в двоичном представлении), способна работать до тех пор, пока не остановится, дав на выходе ответ (в таком же двоичном представлении). Основной вывод, следующий из тезиса Чёрча – Тьюринга, заключается в том, что общего решения Entscheidungsproblem не существует.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Джон Дрейер

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