Машина Поста

МУНИЦИПАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

«Средняя  общеобразовательная школа № 40» 
 
 
 
 

Реферат по Математическим основам информатики  
 

на  тему: « Машина Поста» 
 
 
 
 
 
 
 
 
 
 

      Выполнила:

      ученица  11 «Б» класса 

                                                                                     МОУ СОШ № 40

      Чичкина Екатерина

      Проверила:

                                                                         Лукашина Ольга Ивановна 
 
 
 
 

г. Дзержинск

2010 –  2011 уч. год

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

Теория   алгоритмов  не  учит  "составлять"  алгоритмы.  Она

занимается более  важным вопросом.  Основная  задача  классической

теории  алгоритмов - это ответ на вопрос: " Можно  ли (вообще) для

задач   данного   типа   построить   алгоритм?".   Говоря   более

наукообразно:  "Являются  ли  задачи  данного  типа алгоритмически

разрешимыми"?

Для  любой  алгоритмически разрешимой задачи можно  построить

     рекурсивную  функцию  (машину  Тьюринга, нормальный алгорифм

     Маркова).   И   наоборот,  для задач,  для которых нельзя

     построить   перечисленные   конкретизации,   не   существует

     алгоритма  решения. 

     РЕКУРСИВНЫЕ  ФУНКЦИИ основаны на той идее, что исходные даные

и возможные  результаты решения любой задачи можно  пронумеровать.

Для  чего,  естественно,  достаточно  множества  натуральных чисел

(целых положительных  чисел, начиная с  нуля).  А  далее  базовыми

об'являются функции, возможность выполнить (вычислить) которые не

вызывает сомнений.

     НУЛЬ-ФУНКЦИЯ  -  это функция, которая дает  значение ноль для

любого значения  аргумента.  Реализовать  эту  функцию  может  не

только  ребенок.  Можно  посадить попугая и подучить его на любой

вопрос о значении функции кричать "Ноль!".

     ФУНКЦИЯ   СЛЕДОВАНИЯ   дает   следующее,   по   сравнению  с

аргументом, значение. Для пяти это шесть, для миллиона -  миллион

один.  Можно  бы было сказать, что здесь надо просто прибавлять 1.

Но операции сложения у нас пока нет!

     ФУНКЦИЯ   ВЫБОРА  АРГУМЕНТА.  Это  вообще  забавная  даже для

первоклассника  функция, содержащая в своем имени  номер аргумента.

Если  у  вас  есть несколько аргументов, то эта  функция в качестве

значения возьмет  значение указанного в ней  аргумента.  Например,

функция  выбора  третьего из Иванова, Петрова и Сидорова, которых

мы ранее пронумеровали, например, как 22, 13 и 49,  даст значение

49.

     Эти   три  базовых  функции   могут  использоваться  далее   в

качестве исходного  материала для создания более  сложных функций с

помощью  трех операторов: суперпозиции,  примитивной  рекурсии  и

наименьшего корня.

     Известный   хорошо   еще   со  школы   ОПЕРАТОР  СУПЕРПОЗИЦИИ

позволяет вместо аргумента подставлять функцию... "Игла в яйце, а

яйцо в ларце"...

     Дольше  словами  описывать ОПЕРАТОР  ПРИМИТИВНОЙ РЕКУРСИИ. Но

если поднатужиться, то  можно  понять.  Этот  оператор  позволяет

построить новую  функцию из двух функций, одна из которых  имеет на

один аргумент меньше, а другая на один аргумент больше.

     Значение   создаваемой   функции   для   нулевого   значения

выбранного аргумента  приравнивается к функции, не имеющей  как раз

этого  аргумента. Значение же создаваемой функции  для всех прочих

(ненулевых) значений  выбранного аргумента  приравнивается  другой

функции,  зависящей  (напрягитесь!)  от  тех же аргументов, кроме

выбранного; от ПРЕДЫДУЩЕГО значения  выбранного  аргумента  и  от

создаваемой функции  от предыдущего значения выбранного аргумента.

Последний   оператор   -  ОПЕРАТОР  НАИМЕНЬШЕГО  КОРНЯ.  Его

необходимость просто  об'яснить  хотя  бы  тем,  что рекурсивные

функции, призванные решать любые алгоритмически разрешимые задачи,

сами  используют  лишь  целые  положительные  числа.  А  это   не

позволяет  решить  даже  детскую  задачку:  5  -  8  = ? (Нет для

рекурсивных функций  отрицательных чисел). На  самом-то  деле  эти

детские  задачки  можно  решить по-детски. Договориться, что 1000

это  (сдвинутый)   ноль,   а   вычитание   -   есть   сложение с

"отрицательным"  числом!

Базовые  функции  и функции, которые могут быть построены из

них с помощью  операторов  суперпозиции,  примитивной  рекурсии  и

наименьшего   корня,   образуют   множество  ЧАСТИЧНО-РЕКУРСИВНЫХ

ФУНКЦИЙ. А множество  частично-рекурсивных  функций  совпадает  с

множеством  всех алгоритмически разрешимых задач (множеством всех

вычислимых  функций).   Кстати,   за   слово   "частичные"   надо

благодарить   оператор   наименьшего   корня,  из-за  которого  в

множество построенных  функций  входят  и  не  всюду  определенные

(частичные) функции.

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

предполагает  двигателя внутреннего сгорания,  поскольку  все  там

перемещается   исключительно   силой  мысли.  Это  математическая

модель. Она чем-то может и напоминающая автомашину, но  не  более

чем машину напоминает магнитофон, в котором лента (разделенная  на

ячейки) неподвижна, а считывающе-записывающая головка вдоль нее

ездит.  Хуже того, ездит головка рывками, от ячейки к ячейке. А в

ячейках записаны символы. (Чтобы не было пустых ячеек,  в пустые

ячейки записывают специальный пустой символ) 

     В  машине Тьюринга есть устройство  управления, имеющее память

"состояний"  и работающее  по  задаваемой  программе  (алгоритму).

Программа   состоит   из  команд.  Каждая  "команда"  состоит  в

следующем: Машина читает символ из ячейки, против  которой стоит

головка (находясь в каком-то состоянии  [вначале - в  начальном]),

записывает в  эту ячейку символ (может и  тот  же  самый),  меняет

свое  состояние  (может сохранить прежнее) и делает шаг влево или

вправо (может  остаться на месте).

     Так   Машина ходит вдоль ленты до  тех пор, пока не перейдет  в

специальное состояние, называемое заключительным. Это говорит  об

окончании   работы  Машины  (алгоритма).   А на  ленте остается

результат (решения).

     Пример.     Построим    Машину,    которая    в    сплошной

последовательности  единичек стирает последнюю.

     Поскольку   количество единичек в сплошной  последовательности

произвольное  и неизвестное, последнюю определим  как  ту,  которая

стоит  ПЕРЕД  пустым символом.  Это главная  идея данного решения.

Остальное - дело техники.  Напишем программу - четыре команды.

     Машина  читает пустой символ, находясь  в начальном состоянии

пишет пустой символ и делает шаг вправо. (Значит машина находится

ДО начала последовательности единичек)

     Машина  читает  единичку,  находясь  в   начальном состоянии,

пишет единичку и делает шаг вправо, оставаясь  в  этом  состоянии.

(Значит машина "идет" по последовательности  единичек)

     Машина  читает пустой символ, находясь  в начальном состоянии,

пишет пустой символ, делает  шаг  влево  и  переходит  во  второе

состояние. (Значит найдена последняя единичка)

     Машина  читает единичку, находясь во  втором состоянии, пишет

пустой символ (стирает единичку), стоит на месте  и  переходит  в

заключительное  состояние.  (Задача решена)

     Несмотря  на  внешнюю  примитивность   такой конструкции, для

любой алгоритмически разрешимой  задачи  можно  построить  Машину

Тьюринга!  А  поскольку  машина  строится  в  собственной голове,

вопросы "технической  эффективности" такой машины никакой  роли не

играют.    Единственный    вопрос.   Доберется   ли   машина   до

заключительного состояния? Пусть и  через  (воображаемый) миллион

лет. Тогда задача разрешима! 

     Не  будет  преувеличением  сказать,  что нормальные алгорифмы

Маркова создал  А.А.Марков, член-корреспондент Академии Наук СССР

из  Москвы.  Для восстановления единообразия, по праву автора, он

назвал алгориТмы алгориФмами, поскольку слово это арабо-греческое,

как и слово  ариФметика...

     Смысл   нормальных алгорифмов - принудительный обмен, порядок

которого жестко задан.

     Собственно   алгоритм   в   нормальных  алгорифмах  задается

НОРМАЛЬНОЙ СХЕМОЙ ПОДСТАНОВОК - очередностью правил "что  на  что

менять".  Лучше  всего  это  показать на примере  замены слов, тем

более, что и  сам Марков любую последовательность букв, какую ни в

одном словаре  не сыщешь, называл "словами".  Так при наличии двух

подстановок: меняющей "ха" на "ссон" и "мусс" на "сл"  из  "муха"

можно сделать "слон".

     Механизм   нормальных   алгоритмов   настолько   прост,  что

напоминает скорее детскую игру, чем математику. Но на самом  деле

это  очень  мощный  механизм, поскольку через  него можно выразить

решение любой  алгоритмически разрешимой задачи. И  опять напомним,