МАШИНЫ ТЬЮРИНГА
Алфавит –любое непустое конечное множество, элементы алфавита называются буквами. Словом длины n (n Î N) над алфавитом А называется отображение u: [1; n ]→ A.
Пример. Пусть А ={|; *}, n = 5, u (1) = |, u (2) = |, u (3) = *, u (4) = |, u (5) = *. Тогда u = ||*|*.
Пусть u и v – слова над алфавитом А длины n 1 и n 2 соответственно. Упорядоченной склейкой слов u и v называется слово uv длины n 1 + n 2, заданное следующим правилом:
Пример. Пусть А ={|; *}, u = ||*|*, v = **|. Тогда uv = ||*|***|, vu = ***|*.
Пусть А – алфавит и . Назовем Λ пустым символом, а - алфавитом с пустым символом.
Бесконечной записью конечного слова над алфавитом А в алфавите с пустым символом называется отображение , удовлетворяющее следующим условиям: существуют n 1 < n 2 (n 1, n 2 Î Z) такие, что:
1)
2)
Длиной слова называется величина n 2 - n 1 +1. f (n 1) называется первой буквой слова, f (n 1 +1) – второй буквой, …, f (n 2) – последней (n 2 - n 1 +1)-й буквой.
Бесконечная запись конечного слова иначе называется записью слова на бесконечной ленте. Эта запись привязана к конкретному участку ленты
|
|
Пусть n Î Z. Сдвигом tn называется отображение , заданное правилом .
Теорема 15.1. Множество сдвигов относительно операции композиции образует абелеву группу.
Пусть - алфавит с пустым символом. На множестве бесконечных записей конечных слов над А введем отношение ~ следующим образом:
u ~ v Û
Теорема 15.2. Отношение ~ является отношением эквивалентности.