Тьюринг. Компьютерное исчисление. Размышления о думающих машинах - [10]
Напротив, если программа остановка (Р, Р) вернет ответ «Истина», так как программа Р остановит свое выполнение, получив в качестве входных данных величину Р, тогда программа парадокс Р не остановится, возвращая значение «Ложь». Принимая во внимание все противоречия, Тьюринг сделал вывод, что программа остановка (или halt) не позволяет оценить Р. Другими словами, проблема остановки неразрешима.
Хотя и не существует программы, которая служила бы универсальным инструментом для удовлетворительного решения проблемы остановки, ученые решили, что можно написать программу, дающую ответы на отдельные случаи, то есть, говоря современным языком, частные программы. Этот класс программ был назван программами PHS (partial halting solver), или программами, частично решающими проблему остановки. Однако со временем ситуация была сочтена такой же неразрешимой, как и с проблемой остановки. Вновь используя язык BASIC-256, напишем программу, которая получает на вход программу Р$. Задача состоит в получении на выходе (output) сообщения о том, останавливается ли выполнение программы Р$:
input Р$
if Р$ = "halt" then
print «программа останавливается ДА»
else
print «программа останавливается НЕТ»
endif
end
Мы приходим к поистине разочаровывающему выводу: нет уверенности, что такая простая с виду программа вернет пользователю корректный результат. Удивительно, что еще до появления компьютера и программного обеспечения Тьюринг смог прийти к выводу, что не существует механической процедуры, то есть машины Тьюринга или современной компьютерной программы, которая могла бы определить, остановится ли другая программа (или машина Тьюринга), получив на вход определенные данные. Этот вывод Тьюринг получил с помощью собственного изобретения — машины Тьюринга. Это еще раз доказывает гениальность ученого, который за свою короткую жизнь смог стать величайшим человеком XX века.
Современный компьютер можно считать машиной Тьюринга, имеющей внутри себя еще одну такую машину. Для пояснения этой идеи приведем в пример один из первых компьютеров, ENIAC (Electronic Numerical Integrator And Computer). Этот мастодонт начала компьютерной эры может быть представлен как машина Тьюринга с тремя лентами: одна лента — для считывания входных данных, другая — для записи и возвращения результата, а третья выполняла роль памяти.
В современном компьютере машина Тьюринга, имевшаяся в ENIAC, должна быть изменена, принимая во внимание, что входящая лента раздваивается на вспомогательную память (например, жесткий диск, SD- или флеш-карта) и клавиатуру. В такой машине в виде ленты выхода можно представить монитор, лента памяти соответствует RAM (ОЗУ). Если мы будем рассматривать операционную систему (разные версии Windows Microsoft, или Linux/Unix, или Mac OS) как машину Тьюринга, получится, что совокупность программ, позволяющих управлять ресурсами компьютера, — это машина Тьюринга, контролирующая другую такую же машину, которой является сам компьютер. Кроме того, когда программист пишет программу — совокупность инструкций, то есть исходный код, — он, в свою очередь, должен перевести эти инструкции в машинный или двоичный вид с помощью компилятора, который также можно считать машиной Тьюринга. После преобразования программа может быть выполнена микропроцессором — важнейшим устройством в компьютере. Лежащая в основе всего модель представляет и компьютер, и программу, с помощью которой мы переводим программы на язык, делающий возможным их выполнение, и операционную систему как машины Тьюринга. Другими словами, «все это программы, все это software», к которым нужно добавить электронные схемы, hardware, как будто бы речь идет о software, — эта важная идея является следствием разработок Тьюринга.
Как ни парадоксально это звучит, машина Тьюринга никогда не была воплощена в жизнь самим автором, несмотря на его самоотверженные усилия. Это устройство было и осталось теоретическим, но с его помощью стало возможным определить, какие вопросы могут быть решены с помощью компьютера. Однако исследователи и любители компьютеров по всему миру создали машины, в основе которых лежали теоретические разработки Тьюринга.
Одна из первых моделей появилась в 1972 году в Университете Брандейса в Массачусетсе (США). Ее создатель Ира Гилберт преследовал цель обучать студентов основам информатики. Чуть позже появилось несколько версий машины Тьюринга из деталей LEGO. С помощью соединяющихся друг с другом пластиковых кубиков Денис Кузено построил машину Тьюринга, хотя эта модель не была полностью автоматизирована. Для хранения в программируемом микроконтроллере таблицы переходов в ней применялись «умные» кубики LEGO RCX, использующиеся любителями-робототехниками. Еще одна модель машины Тьюринга была построена с помощью LEGO японцем Джо Нагатой. В 2010 году Майк Дейви создал винтажную модель в память о машине, описанной в работе Тьюринга, которая была опубликована в 1936 году. В его устройстве были использованы микроконтроллер Parallax Propeller и SD-карта, на которой хранились данные о состояниях машины.
Жизнь — одно из самых прекрасных и сложных явлений на планете, изучением которого с начала XX века занимается не только одна биология. Физики, а затем и математики обнаружили, что некоторые биологические явления можно описать с помощью математического языка. Так родилась новая дисциплина — математическая биология, или биоматематика. Благодаря ей сегодня можно получить ответы на множество важных вопросов, касающихся биологии и биомедицины. Эта книга представляет собой панорамный обзор различных явлений, которые изучает биоматематика.
Ежемесячный научно-популярный и научно-художественный журнал.
Эта книга – захватывающий триллер, где действующие лица – охотники-ученые и ускользающие нейтрино. Крошечные частички, которые мы называем нейтрино, дают ответ на глобальные вопросы: почему так сложно обнаружить антиматерию, как взрываются звезды, превращаясь в сверхновые, что происходило во Вселенной в первые секунды ее жизни и даже что происходит в недрах нашей планеты? Книга известного астрофизика Рэя Джаявардхана посвящена не только истории исследований нейтрино. Она увлекательно рассказывает о людях, которые раздвигают горизонты человеческих знаний.
Наше здоровье зависит от того, что мы едим. Но как не ошибиться в выборе питания, если число предлагаемых «правильных» диет, как утверждают знающие люди, приближается к 30 тысячам? Люди шарахаются от одной диеты к другой, от вегетарианства к мясоедению, от монодиет к раздельному питанию. Каждый диетолог уверяет, что именно его система питания самая действенная: одни исходят из собственного взгляда на потребности нашего организма, другие опираются на религиозные традиции, третьи обращаются к древним источникам, четвертые видят панацею в восточной медицине… Виктор Конышев пытается разобраться во всем этом разнообразии и — не принимая сторону какой-либо диеты — дает читателю множество полезных советов, а попутно рассказывает, какова судьба съеденных нами генов, какую роль сыграло в эволюции голодание, для чего необходимо ощущать вкус пищи, что и как ели наши далекие предки и еще о многом другом…Виктор Конышев — доктор медицинских наук, диетолог, автор ряда книг о питании.Книга изготовлена в соответствии с Федеральным законом от 29 декабря 2010 г.
Исаак Ньютон возглавил научную революцию, которая в XVII веке охватила западный мир. Ее высшей точкой стала публикация в 1687 году «Математических начал натуральной философии». В этом труде Ньютон показал нам мир, управляемый тремя законами, которые отвечают за движение, и повсеместно действующей силой притяжения. Чтобы составить полное представление об этом уникальном ученом, к перечисленным фундаментальным открытиям необходимо добавить изобретение дифференциального и интегрального исчислений, а также формулировку основных законов оптики.
Петр Ильинский, уроженец С.-Петербурга, выпускник МГУ, много лет работал в Гарвардском университете, в настоящее время живет в Бостоне. Автор многочисленных научных статей, патентов, трех книг и нескольких десятков эссе на культурные, политические и исторические темы в печатной и интернет-прессе США, Европы и России. «Легенда о Вавилоне» — книга не только о более чем двухтысячелетней истории Вавилона и породившей его месопотамской цивилизации, но главным образом об отражении этой истории в библейских текстах и культурных образах, присущих как прошлому, так и настоящему.
Научно-популярный журнал «Открытия и гипотезы» представляет свежий взгляд на самые главные загадки вселенной и человечества, его проблемы и открытия. Никогда еще наука не была такой интересной. Представлены теоретические и практические материалы.