рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Машина Тьюринга

Машина Тьюринга - раздел Изобретательство, Ручной этап развития вычислительной техники Алан Мэтисон Тьюринг - Выдающийся Английский Математик, Совершивший Грандиозн...

Алан Мэтисон Тьюринг - выдающийся английский математик, совершивший грандиозное открытие, которое положило начало компьютерной эре. В свои неполные 24 года он мысленно сконструировал абстрактный механизм, призванный решить одну из фундаментальных проблем математики, поставленную знаменитым немецким профессором Давидом Гильбертом в 1900 г. на парижском Международном конгрессе математиков. Тем самым Тьюринг не только дал четкий ответ на эту конкретную задачу, но и - что гораздо важнее - сформировал научную основу алгоритма и предвосхитил архитектуру современных компьютеров. Более того, сама идея решения задач путем конструирования абстрактных механизмов, исполняемых на электронных устройствах, стала важнейшей для зарождения новой профессиональной сферы интеллектуальной деятельности - программирования. Тьюринг показал, что не существует "чудесной машины", способной решать все математические задачи. Но продемонстрировав ограниченность возможностей, он на бумаге построил то, что позволяет решать очень многое и что мы теперь называем словом "компьютер".

Машина Тьюринга имеет бесконечную в обе стороны ленту, разделенную на квадратики (ячейки). В каждой ячейке может быть записан некоторый символ из фиксированного (для данной машины) конечного множества, называемого алфавитом данной машины. Один из символов алфавита выделен и называется "пробелом", предполагается, что изначально вся лента пуста, то есть заполнена пробелами.

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

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

· произвольное конечное множество A (алфавит); его элементы называются символами;

· некоторый выделенный символ a0 из A (пробел, или пустой символ);

· конечное множество S, называемое множеством состояний;

· некоторое выделенное состояние s0 из S, называемое начальным;

· таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже);

· некоторое подмножество F, входящее в S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается).

Таблица переходов устроена следующим образом: для каждой пары (текущее состояние, текущий символ) указана тройка (новое состояние, новый символ, сдвиг). Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x {-1,0,1}, определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1).

Детерминированность машины Тьюринга породила ложные представления об истинных возможностях компьютеров и воззрениях самого Алана Тьюринга.Немногие знают, что в 1951 г. Тьюринг выступил в Манчестере с лекцией "Интеллектуальные машины. Еретическая теория" (развитие его работы 1948 г.). Он сказал: "Моя точка зрения такова: можно сконструировать машины, которые весьма близко смогут моделировать поведение человеческого разума. Порой они будут ошибаться, а иногда смогут выдавать новые весьма интересные утверждения, и в целом их выводы будут заслуживать внимания в такой же степени, как и сделанные человеческим разумом. Данное утверждение основывается на ожидаемой большой частоте истинных утверждений, и я думаю, что ему нельзя дать строгое обоснование".

Тьюринг отмечает в своей лекции важнейший момент: "Я уверен, что опасность того, что математик сделает ошибку, является неизбежным следствием его способности порой находить принципиально новый метод. Похоже, это подтверждается хорошо известным фактом, что наиболее надежные люди обычно не обнаруживают действительно новых методов". Вот он, ключ к разгадке тайн мышления. Как ни парадоксально, именно возможность ошибок в мыслительном процессе машины открывает перспективы ее интеллектуальной мощи. Тьюринг завершает свою лекцию пророчеством: "Нужно было бы приложить массу усилий, пытаясь, скажем, мыслить на равных с машиной, поскольку представляется вероятным, что как только начнется машинный способ мышления, ему не потребуется много времени, чтобы превзойти наши слабые мыслительные способности. Не возникал бы вопрос о смерти машин, и они могли бы быть способны общаться друг с другом, оттачивая свой разум. Таким образом, на некотором этапе мы могли бы ожидать, что машины получат власть, как описано в "Эрехоне" Сэмюэла Батлера".

 

– Конец работы –

Эта тема принадлежит разделу:

Ручной этап развития вычислительной техники

Развитие механики в xvii в стало предпосылкой создания вычислительных устройств и приборов использующих механический принцип вычислений такие.. комплекс холлерита машина.. машина поста..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Машина Тьюринга

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Ручной этап развития вычислительной техники
Ручной этап развития ВТ начался на заре человеческой цивилизации - он охватывает период от 50 тысячелетия до н.э. и до XVII века. Фиксация результатов счета у разных народов на разных континентах п

Устройство Леонардо да Винчи
Своего рода модификацию абака предложил Леонардо да Винчи (1452-1519) в к

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

Машина Паскаля
Первая действующая модель счетной суммирующей машины была создана в 1642

Машина Бэббиджа
Аналитическая машина Бэббиджа представляла собой единый комплекс специализированных блоков. По проекту она включала следующие устройства. Первое - устройство для хранения исходных данных и промежут

Машина Лейбница
Машина, созданная Лейбницем в 1694 г., давала возможность механического в

Другие машины
Во второй половине XIX века появилось целое поколение механических счетных машин. Здесь и "вычислительный снаряд" Слонимского, и оригинальные счетные машины Фельта, Берроуза, Боле, и ариф

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

Принцип работы
Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции ленты, считающейся условно бесконечной в обе стороны. В каждой клетке может быть записан символ из фикс

Этап электронно-вычислительных машин
С начала 1990-х годов термин "компьютер" вытеснил термин "электронная вычислительная машина" (ЭВМ), которое, в свою очередь, в 1960-х годах заменило понятие "цифровая вычис

Персональный компьютер
Персональный компьютер - компьютер, специально созданный для работы в однопользоват

Поколение эвм и суперкомпьютеры
Сейчас ведутся интенсивные разработки ЭВМ V поколения. Разработка последующих поколений компьютеров производится на основе больших интегральных схем повышенной степени интеграции, использования опт

Суперкомпьютеры
Однако мощности будут продолжать расти. Это необходимо для решения глобальных задач, таких как расчет аэродинамики автомобилей и свойств разнообразных наноструктур, ЗD-моделирование. ЭВМ, имеющие м

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги