Машина Тьюринга и проблемы остановки

НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

БАЛТИЙСКИЙ  ИНСТИТУТ ЭКОНОМИКИ  И ФИНАНСОВ 
 
 
 
 
 

     Контрольная работа по Концепции современного естествознания 

     по  теме: Машина Тьюринга и проблемы остановки 
 
 
 
 
 
 
 
 
 

                             Выполнила:

                                                      Студентка 1 курса, группы                  

                      3016-БА

                                                          Тарасенко Ирина Николаевна 

                          Проверил:

                            Юров А.В. 
 
 
 
 
 
 
 
 

     Калининград 2010 
 

     Содержание: 
 
 
 

Введение……………………………………………………………………....3

1.Тьюринг  Алан Матисон – биография……………………………………..4

2. Описание  машины Тьюринга……………………………………………..4

3. Свойства  машины Тьюринга как алгоритма……………………………..6

4. Сложность  алгоритмов…………………………………………………….7

5. Сложность  проблем………………………………………………………..8

6. Машина  Тьюринга и алгоритмически неразрешимые  проблемы……...10

Заключение…………………………………………………………………...13

Список  использованной литературы………………………………………..14 
 

 

      Введение 

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

     Почти за каждым выдающимся научным открытием  стоит удивительная история. За "машиной  Тьюринга" стоит история жизни  научного гения — гения, который  лишь через много лет после  своей трагической смерти получил достойное признание.

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

     Алан  Тьюринг может быть причислен  к плеяде составляющих гордость человечества величайших математических и философских  умов, таких, как Р.Декарт, Г.В. Лейбниц, Б.Рассел, Д.Гильберт, А.Витгенштейн. Удивительно, сколь злую шутку сыграло с  Тьюрингом его полное безразличие к борьбе за приоритет в научных открытиях: вплоть до недавнего времени его место в истории развития научных и инженерных идей представлялось очень неполно, если не сказать однобоко (и не в последнюю очередь благодаря некоторым американским историкам науки, тщательно заботившимся об абсолютизации своего национального приоритета в создании компьютеров, да и пожалуй, в создании всей информатики).

     Мемориальная  доска, установленная чуть больше года назад на стене одной из лондонских гостиниц, гласит:

     "Здесь  родился Алан Тьюринг (1912 —  1954), взломщик кодов и пионер  информатики ". Действительно,  сейчас (но отнюдь не при жизни!) Тьюринг признан одним из основателей  информатики и теории искусственного  интеллекта, его считают первым  теоретиком современного программирования и, наконец, первым в мире хакером. (Между прочим, его "хакерская деятельность" внесла во время второй мировой войны существенный вклад в победу союзных войск над германским флотом , а один из коллег Тьюринга однажды сказал: "Я не берусь утверждать, что мы выиграли войну благодаря Тьюрингу.  
 
 
 
 
 

     1.Тьюринг Алан Матисон – биография. 

     Алан  Матисон Тьюринг родился 23 июня 1912- 7 июня 1954) — английский математик, логик , криптограф, оказавший существенное влияние на развитие информатики. Предложенная им в 1936 году абстрактная вычислительная «Машина Тьюринга» позволила формализовать понятие алгоритма и до сих пор используется во множестве теоретических и практических исследований.

     Жизнь Алана Тьюринга закончилась трагически. Он был признан «одной из самых известных жертв гомофобии в Великобритании».

     Сын британского чиновника в Индии, Алан учился во Франции, Англии и, затем, в США. Тогда многие математики пытались создать алгоритм для определения  истинности высказываний.

     Но  Гёделю удалось доказать, что любая полезная математическая система аксиом неполна в смысле, что в ней существует высказывание, истинность которого нельзя ни опровергнуть, ни подтвердить. Это побудило Тьюринга доказать, что нет общего метода определения истинности и, таким образом, математика всегда будет содержать недоказуемые высказывания.

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

     Когда Тьюринг из США возвратился в  Англию, началась вторая мировая война. . Одним из важнейших вооружений этой войны была ЭВМ «Колосс» по проекту «Ультра», начавшая в 1943 году взламывать сверхсложные шифры немцев. Работа этой системы значительно помогла союзникам в борьбе с немецко-фашистскими захватчиками.

     8 июня 1954 года Алан Мэтисон Тьюринг  был найден мертвым в своем  доме — отравился цианидом. Яблоко, начиненное этой отравой, лежало рядом на ночном столике. До сих пор точно не известно , было ли это самоубийством или Тьюринга погубили завистники. Его мать считала, что он отравился случайно, так как всегда небрежно работал с химикатами. 
 

     2. Описание машины Тьюринга 

     Алан  Тьюринг (Turing) в 1936 году опубликовал  в трудах Лондонского математического  общества статью "О вычислимых числах в приложении к проблеме разрешения", которая наравне с работами Поста  и Черча лежит в основе современной теории алгоритмов.

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

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

     Приведем  характеристику этой работы, принадлежащую Джону Хопкрофту: "Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга".

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

     Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:

     конечное  множество состояний – Q, в которых  может находиться машина Тьюринга;

     конечное  множество символов ленты – Г;

     функция δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х {L,R}

     один  символ из Г-->е (пустой);

     подмножество  Σ є Г - -> определяется как подмножество входных символов ленты, причем е  є (Г - Σ);

     одно  из состояний – q0 є Q является начальным состоянием машины.

     Решаемая  проблема задается путем записи конечного количества символов из множества Σ є Г – Si є Σ на ленту:

     eS1S2S3S4... ... ... Sne

     после чего машина переводится в начальное  состояние и головка устанавливается  у самого левого непустого символа (q0,­w) –, после чего в соответствии с указанной функцией переходов (qi,Si) - ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

     Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.

     Алан  Тьюринг высказал предположение, что  любой алгоритм в интуитивном  смысле этого слова может быть представлен эквивалентной машиной  Тьюринга. Это предположение известно как тезис Черча–Тьюринга. Каждый компьютер может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины). Следовательно, он может моделировать алгоритмы в любом формализме, и из этого тезиса следует, что все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности решения алгоритмических задач.  

     3. Свойства машины Тьюринга как алгоритма 

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

     Дискретность. Машина Тьюринга может перейти к (к + 1) - му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) - й шаг.

     Понятность. На каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных состояний.

     Детерминированность. В каждой клетке таблицы машины Тьюринга записан лишь один вариант действия. На каждом шаге результат определен однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т.е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же.

     Результативность. Содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0, т.е. за конечное число шагов будет получен ответ на вопрос задачи.

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

                                    

     4. Сложность алгоритмов