Лекция 1 Теория алгоритмов и математическая логика Функция

Функция, отображающая множество Xво множествоYобозначаетсяи называется подмножествомFдекартовых произведенийX×Y, причём.

Множество всех x, для которых, называется областью определения функции:. Множество всехyтаких, что, называется областью значения:.

Функция ─ всюду определённая функция, если её область определения совпадает с множествомX, в противном случае функция называется частичной.

Функция называется n-местной функцией над множествомM, еслиY=M,X=Mⁿ=M×M×M×…×M.

Суперпозицией двух функций иназывается функция, такая что, еслитакой, чтои. Обозначается как.

Предикатом называют функцию, областью значения которой служит множество символов 0 и 1. Говорят, что предикат истинен для, еслии предикат ложен, если. Отношение на любом множествеXпредставляет собой двуместный предикат:.

Словарные функции

Слово или цепочка употребляются в одном и том же смысле.

Алфавит – конечное, непустое множество символов.

V= {a₁, a₂, …, a_n}

Цепочкой в алфавите Vназывается конечный объект, получаемый выписыванием одного за другим символов из алфавитаV.

Для V= {0, 1, 2, …, 9} цепочкой является натуральное число.

Длина цепочки есть количество символов в ней. |α| - длина цепочки.

Пустая цепочка не содержит ни одного элемента (ε) алфавита. Пустая цепочка не есть символ пробела.

Множество всех цепочек (включая и пустую) над алфавитом VобозначаетсяV*.

n-местной словарной функцией над алфавитом Vназывается n-местная функция над множествомV^*. V^*×V^*×V^*×…×V^*→V^*.

В качестве двуместной словарной функцией может выступать операция конкатенации. Цепочка γ называется подцепочкой цепочкой α, если α представляет собой конкатенацию α=υγω, где ω,υ – возможные цепочки. При этом γ называется префиксом цепочки α, если цепочка υ пустая, или суффиксом, если ω пустая.

Существует взаимнооднозначное соответствие между неотрицательным целым числом и цепочкой в произвольном алфавите V. Символы алфавитаVможно произвольным образом упорядочить, перенумеровать их числами {1,2,…,n}. Задаётся функция упорядочивания. Пустой цепочке поставим в соответствие число 0, а остальные цепочки упорядочим по следующим правилам.

Если |α|<|β|, то α располагается левее β.

Если цепочки имеют одинаковую длину, то они упорядочены в алфавитном порядке, т.е. с учётом порядковых номеров символов алфавита.

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

Вычислимые функции и машина Тьюринга

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

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

Машина Тьюринга Tзадаёт словарную функцию под некоторый алфавит V и представляет собой описание машины, т.е. набор объектов (V, Q, q0, #, I).

V– алфавит машины

Q– алфавит состояний,

q₀ – начальное состояние,

# - пустой символ,

I – программа машины Тьюринга

Программа – конечное множество цепочек вида qa→q΄a΄d, которые называется командами.

В каждой цепочке

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

Функционирование машины Тьюринга может быть описано следующим образом. Предполагается, что машина Тьюринга работает с потенциальной бесконечной в обе стороны лентой управления, под которой перемещается считывающая - записывающая головка. Лента разбита на ячейки, в которых могут быть записаны символы из алфавита Vили пустой символ#. Расшифровав программу, которая однозначно определяет поведение машины и управление головкой, мы получаем работу машины Тьюринга. Головка в каждый момент времени расположена напротив одной ячейки ленты. Символ, находящийся в ячейке, считывается, после чего машина Тьюринга записывает некоторый символ и либо остаётся на месте, либо сдвигается влево или вправо.

Машина работает по программе следующим образом.

В начальный момент времени на ленте записывается некоторая цепочка из множества V^*, все остальные клетки ленты заполнены символом#. Управление в начальный момент находится в состоянииq₀, считывающая – записывающая головка обозревает крайний слева символ. Работа машины состоит в повторе следующего цикла элементарных действий:

1. Чтение головкой символа из ячейки напротив.

2. Поиск применимой команды, а именно команды qa → q’a’d, гдеq-некоторое состояние управления,a-считываемый символ.

3. Выполнение найденной команды, которая состоит в следующем. В обозреваемую головкой ячейку записывается символ a’, символa-стирается, управление переходит в состояниеq’ и головка смещается относительно d. Еслиd=rголовка смещается на одну ячейку вправо, еслиl - смещается на одну ячейку влево,p – перемещение не производится. Остановка производится в том случае, если на очередном шаге ни одна команда программы не является применимой. Результатом работы машины Тьюринга является цепочка, записанная на ленте.