Курсовая работа (т): Понятие предиката. Множество истинности предиката. Классификация предикатов

Понятие предиката. Множество истинности предиката. Классификация предикатов

Курсовая работа

Понятие предиката. Множество истинности предиката. Классификация предикатов

Введение

тьюринг вычислительный предикат

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

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

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

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

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

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

Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт - «в математике не может быть неразрешимых проблем», в связи с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

Первой фундаментальной теоретической работой, связанной с доказательством алгоритмической неразрешимости, была работа Курта Гёделя - его известная теорема о неполноте символических логик. Это была строго формулированная математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен. В частности, не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.

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

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

1. Машины Тьюринга

1.1 Определение машины Тьюринга

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

Машина Тьюринга есть математическая (воображаемая) машина, а не машина физическая. Она есть такой же математический объект, как функция, производная, интеграл, группа и. т.д. И, так же как и другие математические понятия, понятие машины Тьюринга отражает объективную реальность, моделирует некие реальные процессы. Именно Тьюринг предпринял попытку смоделировать действия математика (или другого человека), осуществляющего некую умственную созидательную деятельность. Такой человек, находясь в определенном «умонастроении» («состоянии»), просматривает некоторый текст. Затем он вносит в этот текст какие-то изменения, проникается новым «умонастроением» и переходит к просмотру последующих записей.

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

Опишем теперь машину Тьюринга более тщательно. Машина располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит А = {, , …, }. В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита А. Ради единообразия удобно считать, что среди букв внешнего алфавита А имеется «пустая буква», и именно она записана в пустую ячейку ленты. Условимся, что «пустой буквой» или символом пустой ячейки является буква . Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.

Далее, в каждый момент времени машина способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых Q = {, , …, }. Среди состояний выделяются два - начальное  и заключительное (или состояние остановки) . Находясь в состоянии , машина начинает работать. Попав в состояние , машина останавливается.

Работа машины определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда Т (i, j) (i=1,2,…, m; j=0,1, …, n) представляет собой выражение одного из следующих видов:

> С; > П; > Л,

где 0 ≤ k ≤ m; 0≤ λ ≤ n. В выражениях первого вида символ С будем часто опускать.

Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (т.е. в состоянии, отличном от ), машина совершает шаг, который полностью определяется ее текущим состоянием  и символом , воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой Т (i, j): > X, где Х  {С, П, Л}. Шаг заключается в том, что:

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

) машина переходит в новое состояние  (оно также может совпадать с предыдущем состоянием );

) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х=П, или к обозрению следующей левой ячейки, если Х=Л, или же продолжает обозревать ту же ячейку ленты, если Х = С.

В следующий момент времени (если  ≠ ) машина делает шаг, регламентированный командой Т (k, l): →Х и т.д.

Поскольку работа машины, по условию, полностью определяется ее состоянием в данный момент и содержимым  обозреваемой в этот момент ячейки, то для каждых  и  (i=1, 2, …, m; j=0, 1, …, n) программа машины должна содержать одну и только одну команду, начинающуюся символами . Поэтому программа машины Тьюринга с внешним алфавитом А={, , …, } и алфавитом внутренних состояний Q ={, , …, } содержит m (n+1) команд.

Словом в алфавите А или в алфавите Q, или в алфавите AQ называется любая последовательность букв соответствующего алфавита. Под k-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-го шага (или слово в алфавите А, записанное на ленту к началу k-го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

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

Будем говорить, что непустое слово ɑ в алфавите А\ {}=, …, } воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово ɑ. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии  (соответственно в состоянии остановки ). Наконец, будем говорить, что слово ɑ перерабатывается машиной в слово b, если от слова ɑ, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову b, воспринимаемому в положении остановки.

1.2 Применение машин Тьюринга к словам

Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга.

Пример 2.1. Дана машина Тьюринга с внешним алфавитом А={0,1} (здесь 0-символ пустой ячейки), алфавитом внутренних состояний Q={,, } и со следующей функциональной схемой (программой):

0→0П; 0→1; 1→1П; 1→1→1П.

Посмотрим, в какое слово переработает эта машина слово 101, исходя из стандартного начального положения. Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение.

Таким образом, исходное слово 101 переработано машиной в слово 10101.

Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите АQ: 101 (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина). Далее, конфигурация (2) записывается так: 1010, конфигурация (3) - 10100 и, наконец, (4) - 10101. Вся последовательность записывается так: