Машина Тьюринга
Статья в разработке
В науке не обязательно решить задачу, иногда именно постановка задачи является самым главным, так как это определяет направление развития на многие годы, в то время как результат, обладая законченной ценностью, уже не несет в себе возможности к развитию. Существует небезосновательное мнение о том, что человек способен привыкнуть и приспособиться к любым условиям жизни. Если физические условия меняются на протяжении одной жизни незначительно, то информационная среда, а следовательно, и правила игры и свойственные им “выигрышные стратегии” гораздо более изменчивы. Те из них, которые были признаны общественным мнением безусловно правильными в период детства и воспитания конкретного человека, всего лишь через несколько десятилетий могут оказаться совершенно бесперспективными, что находится в явном противоречии с необходимостью выживания. Или выживание не является такой уж необходимостью? Ответ на этот вопрос многое бы прояснил в решении конкретных жизненных ситуаций и особенно классической проблемы “отцов и детей”, но, боюсь, единого мнения здесь сформировать не удастся. Каждый принимает решение о степени своей возможной адаптации сам. И каждый прав, но только для себя, какое бы он решение ни принял. Скорее всего, речь идет о неизбежной реализации предопределенной схемы поведения, заложенной генетически и функционирующей в соответствии с биологическим отсчетом времени на протяжении развития индивидуума, либо о “жестком ядре” личности и изменчивой, адаптирующейся внешней оболочке, причем граница между первым и вторым опять-таки определена генетическими особенностями на “аппаратном” уровне.
Но для Тьюринга, самостоятельно изучавшего квантовую физику и теорию относительности еще в школе, этот вопрос был решен однозначно. Он спроецировал на машину свое собственное отношение к миру, а принципы обработки информации, заложенные в нее, несомненно являются результатом интроспекции. Машина Тьюринга – это, прежде всего, модель самого Тьюринга, своеобразный “памятник нерукотворный” собственному интеллекту. Иными словами – особенности мировосприятия Тьюринга наиболее точным образом представляются его машиной.
Машина Тьюринга
Машина Тьюринга – модель вычислительного процесса, в которой каждый алгоритм разбивается на последовательность простых, элементарных шагов и представляет собой логическую конструкцию. Физически она состоит из ленты бесконечной длины, разделенной на ячейки, и головки, которая перемещается вдоль ленты и способна читать и записывать символы.
Была предложена в 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма. Машина Тьюринга – прообраз программируемого компьютера, абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель.
Машина Тьюринга была пригодна для решения любой разрешимой математической или логической задачи. Она предназначалась для выполнения логических операций: она могла читать, писать и стирать символы, записанные в клетках бесконечной ленты. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
Почему надо «знать» машину Тюринга?
Потому, что Тюринг показал, что существуют задачи, которые алгоритмически неразрешимы. Первоначально это вызвало шок и непринятия такого «скверного» определения понятия алгоритм. Были предприняты многочисленные, но безуспешные попытки его «улучшить». Однако еще до Тюринга Геделем была сформулирована теорема о неполноте формальных исчислений.
Тюринг показал на примерах, что существуют задачи, для которых применение формальных методов требует бесконечно много времени для решения, т.е. решения практически нет. В то время как человек решает эти задачи очень просто. Это имеет важное практическое значение для разработчиков систем искусственного интеллекта. Так как определение алгоритма по Тюрингу (или Маркову) говорит, фактически, о невозможности создания систем искусственного интеллекта, которые были бы способны заменить человека. По крайней мере, пока не возникнет новая математика или не появятся биороботы, в которых мозг человека или другого существа будет объединен с возможностями большой вычислительной машины. (а работы в этом направлении уже ведутся).
Почему надо «знать» машину Тюринга? Потому, что это – Начала математики, в нем вводится понятие алгоритм. Тезис Тюринга: всякий алгоритм может быть реализован соответствующей машиной. Этот тезис является формальным определением алгоритма. Он позволяет доказывать существование или несуществование алгоритмов, описывая соответствующие машины Тюринга или доказывая невозможность их построения.
Не знать машину Тюринга – значит не знать математики.
Потому, что это – Начала программирования, в нем вводятся понятия алгоритм. К сожалению, у многих программистов тюринговское определение алгоритма заменяется на своё, более близкое: алгоритм – эта программа, которую пишу Я.
Но если вы не знаете, что такое алгоритм, то как вы можете говорить, что вы запрограммировали алгоритм решения какой-либо задачи.
Потому, что машины Тюринга были использованы в 40-ых годах прошлого века при разработке первых электронных вычислительных машин.
Потому, что, складывая в столбик, чтобы подсчитать свои суммарные денежные затраты, например, мы фактически реализуем машину Тюринга. Действительно, как выполняется сложение в столбик:
587
+
104
________
791
7 + 4 – мы ведь реально не производим вычисления, не прибавляем как школьники первого класса к 7 палочкам еще 4 палочки. Нет, мы знаем что 7+4 = 1 и 1 «в памяти».
Т.е. ее надо перенести влево как это и делается в машине Тюринга. Точно также мы складывая 8 и 0 получаем 8, но так как мы находимся в особом состоянии, которое называется «перенос единицы» мы знаем, что в нижней строке надо записать 9.
Вместо реальных вычислений производится формальная замена одних символов другими. Но интерпретировать записанную последовательность символов «791» как число или как текст или другим образом зависит целиком от нас.
Семантическая интерпретация последовательности символов целиком зависит от контекста, от наших соглашений с другими людьми. Например, FF можно интерпретировать как пару букв латинского алфавита, а можно как число 255, записанное в шестнадцатиричной системе. Так что считать ли FF частью номера автомобиля или числом зависит только от нас.
Еще один пример. Вспомним, что А.Марков дал другое определение алгоритма. Со школьной скамьи мы знаем, что 7х8 = 56. Если кто забыл об этом, то можно освежить свою память, посмотрев на обложку школьной тетради. Здесь имеет место употребления нормальных алгоритмов Маркова. Цепочка символов 7х8 заменяется на цепочку 56. Никаких действий не происходит.
25.01.2013
Материалы по теме:
Маленькая, сухая, улыбчивая старушка. Проницательный взгляд, подвижное лицо, грубые, непропорционально большие натруженные крестьянские руки. В ее присутствии собеседники ощущали себя осмысленной частью творения — она лучезарно и умно смотрела в…
Авторы статьи С.Г. Достовалов и Л.В. Мальцева Зачем нужна мама? На первом году жизни у ребенка устанавливается тесная психологическая связь с матерью. Недостаток материнской любви и внимания в этот период…
Матрица Эйзенхауэра – один из методов тайм-менеджмента для определения приоритетов дел дня. Выглядит матрица как четыре квадрата, которые получаются при пересечении осей “Важно – Неважно” по горизонтали и “Срочно –…
Материнская модель любви воплощают безусловное принятие любимого и отношение к нему как к маленькому ребенку, нуждающемуся в теплоте и бережности, любви и заботе. Материнская модель любви – это не утверждение,…
