Цитаты из книги «Джордж и код, который не взломать»

Люди с давних времён научились кодировать – шифровать – сообщения так, чтобы тем, кто не знает шифра, эти сообщения казались абракадаброй. Это позволяло посылать союзникам тайные послания, которые не сможет прочесть враг. В наши дни всякий, кто что-то покупает в интернете – например, музыку, книги или подарок, – тоже вынужден зашифровывать номер своей банковской

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

до бесконечности. Тьюринг также математически показал, что даже машина Тьюринга не может решить все задачи! Иными словами, некоторые задачи в математике не решаются с помощью вычислительной техники – то есть математиков пока нельзя заменить машинами. Любое возможное вычисление Если есть достаточно времени и есть возможность записать на ленте ввода нужное число единиц, то выполнимо любое механическое действие с целыми числами, какое только можно придумать. Для этого требуется

на момент начала работы справа от управляющего устройства не было ни одной единицы, она бы никогда не остановилась, а продолжала бы движение в вечном и бесплодном поиске единицы. Такое может произойти и с настоящим компьютером: программа может «зациклиться», и в конце концов компьютер сломается. К сожалению, такая возможность – неотъемлемое свойство и машины Тьюринга, и реальных компьютеров. Однако этого легко избежать, если изначально указать, что среди «корректных» входных данных должна быть по меньшей мере одна единица, так, чтобы первое правило не могло применяться

ленте и передвигается ещё на шаг вправо. Всё это повторяется с каждым тиканьем часов, пока наконец машина не достигнет первой единицы на ленте. Теперь требуется правило, объясняющее, что делать, когда процессор читает 1 в состоянии 0. Простейшим правилом будет: оставаться в состоянии 0, записать 1, перейти на шаг вправо и остановиться. Теперь слева от машины будет записана единица, и это будет результат вычисления. Этот алгоритм можно описать как «печатать 1, если входные данные корректны», где «корректны» означает «содержат по меньшей мере одну единицу». Если бы

на ленте, и где-то справа несколько нулей заменены единицами – эти единицы образуют в двоичной системе число, которое мы даём машине в качестве входных данных. Тогда правило для начала работы выглядит так: если в состоянии 0 мы читаем 0 – перейти в состояние 0, написать 0 и перейти вправо. Это означает, что если вначале машина видит 0 (находясь в состоянии 0), она остаётся в состоянии 0, не изменяет запись 0 на ленте и переходит на шаг вправо. Если следующий знак – опять 0, повторяется то же самое: машина остаётся в состоянии 0, не делает отметок на лен

данный момент. Затем он может сделать одно из двух – в зависимости от того, что он прочёл, и от своего текущего состояния. Он может: • изменить прочитанный символ на 0 или 1; сдвинуться по ленте на одну позицию влево или вправо; возможно, перейти в другое состояние; ждать следующего тиканья; • сделать всё то же, после чего остановиться (отключиться). Что именно сделает процессор, зависит от правил («программы»), которые мы зададим, и от того, что он прочтёт на ленте. Предположим, что машина начинает работу в состоянии 0, с длинной цепочкой нулей

как сама лента). Эта лента, которая тянется бесконечно в обоих направлениях (предположим, что она бесконечно длинная), – «память» вычислительной машины. Между нулями вкраплено конечное число единиц – они представляют введённые в машину «данные». На ленте установлено управляющее устройство (процессор). Процессор может читать ровно один символ, проходящий через него в данный момент, и может либо ничего с ним не делать, либо заменить на 0 или 1. Процессор также включает в себя часовой механизм, который ритмично тикает, и с каждым тиканьем процессор читает символ, который видит в дан

То есть машина Тьюринга – не реальный прибор, а математическое устройство, позволяющее понять, что такое вычисление и чего можно достичь путем вычислений. В реальности такой машины быть не может: например, у неё должны быть и бесконечная «память», и неограниченное время работы, а ни то, ни другое невозможно. Цепочка нулей Действие, выполняемое машиной, описывается конечным списком зашифрованных инструкций. Представим себе очень длинную ленту, на которой написана очень длинная цепочка нулей (такая же длинная,

разработан «Колосс» – первая программируемая вычислительная машина на электронных лампах; с помощью «Колосса» взломали код другой немецкой шифровальной машины, которая называлась «Лоренц». Универсальная машина тьюринга Воображаемое устройство В 1936 году «компьютером», то есть «вычислителем», называли не машину, а человека, который что-то вычисляет. Машина Тьюринга, придуманная гениальным математиком Аланом Тьюрингом, – воображаемое устройство, способное воспроизводить всё, что делает в хо де расчётов человек-компьютер.