Том 15. От абака к цифровой революции. Алгоритмы и вычисления - [30]
* * *
В 1947 году в разрушенной послевоенной Германии Цузе возвращается к работе над своими машинами. Он наладил контакты с IBM, а позднее с Remington-Rand, с которой заключил соглашение. Он создал машины на электронных лампах, в частности Z22, и на транзисторах, в частности Z23 и Z3. Позднее ученый разработал Z64 — графопостроитель, управляемый машиной.
Единственным образцом первых машин Цузе, дошедшим до наших дней, стала Z4 — первая коммерческая вычислительная машина. Она использовалась во множестве учреждений вплоть до 1959 года. Один из экземпляров Z4 вместе с воссозданной версией Z3 сейчас хранится в Немецком музее Мюнхена. К сожалению, все остальные машины были разрушены во время бомбардировок Берлина.
Алан Тьюринг (1912–1954) в детстве хотел стать врачом, но в итоге стал математиком, философом и специалистом по криптографии, а также создателем современной информатики. Он известен в первую очередь благодаря своим теоретическим работам, однако также сыграл очень важную роль в практической реализации одного из первых компьютеров. Тьюринг сделал свое первое открытие в теоретической математике в 1936 году, решив проблему разрешения (Entscheidungsproblem), сформулированную Давидом Гильбертом. Чтобы справиться с этой задачей, Тьюринг создал модель вычислений, в которой дал формальное определение алгоритму (или программе). Эта модель вошла в историю под названием машина Тьюринга.
В 1928 году влиятельный немецкий математик Давид Гильберт (1862–1943), который в 1900 году предложил знаменитый список задач, начал работу над проблемой разрешения, которую впервые сформулировал Лейбниц. Гильберт считал, что нерешаемых задач не существует. Он предложил гипотезу, согласно которой всегда можно составить программу (алгоритм), которая сможет дать однозначный верный ответ на любой заданный вопрос. Независимо друг от друга Алан Тьюринг и американский математик Алонзо Чёрч доказали, что Гильберт ошибался: нерешаемые задачи существуют, а предложенную Гильбертом программу (алгоритм) составить невозможно. Следовательно, математика не является разрешимой, то есть не существует метода, который позволил бы определить истинность или ложность произвольного математического утверждения.
Математик Алан Тьюринг, считающийся одним из создателей компьютеров.
Чёрч и Тьюринг в своих доказательствах использовали созданные ими модели: первый применял лямбда-исчисление, второй — разработанную им машину. Оба дали формальное определение алгоритму и использовали в своих доказательствах арифметические задачи. Существование арифметических задач, для которых решения отсутствуют, означало бы, что решить любую произвольную задачу также невозможно. Однако работа Тьюринга была намного более доступной и понятной.
Он свел проблему разрешения к проблеме остановки и доказал, что она неразрешима с помощью его машины: нельзя определить алгоритмически, завершит ли данная машина Тьюринга свою работу в какой-то момент или нет. Чёрч и Тьюринг не соперничали; напротив, оба осознавали, что их модели, несмотря на формальные различия, были одинаково мощными, и объединили усилия.
* * *
КАК РАБОТАЕТ МАШИНА ТЬЮРИНГА?
Представим себе бесконечную ленту, на которой записаны входные символы некой задачи и на которой можно печатать. Машина Тьюринга содержит считывающее устройство, расположенное в определенной части ленты. Это считывающее устройство позволяет выполнять считывание и запись на ленту, а программа машины Тьюринга может перемещать считывающее устройство в заданное положение. Возможные состояния машины представляются посредством множества состояний Q. Программирование машины представляется в виде функции перехода, которая определяет новое состояние на основе текущего состояния и входного символа.
Формально машина Тьюринга определяется на основе кортежа из семи элементов. Кортеж — это упорядоченная последовательность элементов, то есть перечень ограниченного числа объектов. Кортежи используются для описания математических объектов, имеющих структуру. Обозначим кортеж, который будет обрабатывать наша машина Тьюринга, как
МТ = (Γ, Σ, Ь, Q, q>0, f, F).
Его элементы определяются следующим образом.
• Γ — алфавит, символы которого записываются на ленте.
• Σ
• b 
• Q — множество состояний.
• q>0
• f — функция перехода. Для данного состояния и элемента, записанного на ленте, эта функция определяет новое состояние, записывает символ на ленте и перемещает считывающее устройство влево (I), вправо (D) или же оставляет неподвижным (Р). Таким образом, функция f является функцией вида f: Q x Γ —>
