close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Машины Тьюринга
28 января 2014 г.
1
Потоковые алгоритмы
Потоковые алгоритмы имеют несколько существенных отличий от конечных автоматов:
1. Потоковые алгоритмы могут возвращать значения, состоящие более чем из одного бита.
2. Объем “памяти”, используемой потоковым алгоритмом, может (медленно) возрастать по мере увеличения длины входной строки.
3. Потоковые алгоритмы могут совершать несколько проходов по входным данным, могут быть рандомизированы.
Число различных элементов
Вход: x ∈ {1, . . . , 2k }∗ , где 2k > |x|2 .
Выход: Число различных элементов последовательности x.
Существует потоковый алгоритм подсчета числа различных элементов, использующий O(kn) памяти (где n — длина входной строки x).
Теорема 1. Любой потоковый алгоритм подсчета числа различных
элементов использует Ω(kn) памяти.
Определение 1. Пусть Σ = {1, . . . , 2k }. Назовем две строки x, y ∈ Σ∗
различимыми, если найдется строка z ∈ Σ∗ , такая что xz и yz содержат
различное число различных элементов.
1
Лемма 1. Допустим, что всякие две строки в S ⊆ Σ∗ различимы.
Тогда любой потоковый алгоритм подсчета числа различных элементов
использует ≥ log2 |S| бит памяти.
Доказательство. Согласно принципу Дирихле, если алгоритм A использует < log2 |S| бит памяти, в S найдутся различные строки x и y, обработка которых приведет A в одно и то же состояние. Тогда, какой бы ни
была строка z, алгоритм выдаст один и тот же ответ для строк xz и yz,
что противоречит предположению о различимости x и y.
Лемма 2. Существует 2Ω(kn) попарно различимых строк над алфавитом Σ = {1, . . . , 2k } длины не больше n.
Доказательство. Для T ⊆ Σ размера n/2 обозначим за xT строку, полученную из элементов T (упорядоченных по возрастанию). Если T 6= S,
то xT и xS различимы, так как
• xT xT содержит в точности n/2 различных элементов, а
• xS xT содержит более n/2 различных элементов.
Если 2k > n2 , то всего найдется 2Ω(kn) таких подмножеств.
2
Машины Тьюринга
Определение 2. Машина Тьюринга — это семерка
(Q, Σ, Γ, δ, q0 , qaccept , qreject ),
где
Q — конечное множество состояний,
Σ — конечное множество, называемое входным алфавитом,
Γ — конечное множество, называемое рабочим алфавитом,
• ␣ ∈ Γ \ Σ,
• Σ ⊆ Γ,
δ : Q × Γ → Q × Γ × {L, R} — функция переходов,
2
q0 ∈ Q — начальное состояние,
qaccept — допускающее состояние,
qreject — отвергающее состояние
• qaccept 6= qreject .
Отличия машин Тьюринга от конечных автоматов
• Машины Тьюринга могут как записывать данные на ленту, так и
считывать данные с ленты.
• Головка может передвигаться налево и направо.
• Необязательно считывать входные данные целиком. С другой стороны, вычисление может продолжаться (даже бесконечно) после
того, как все входные данные были считаны.
• При достижении допускающего или отвергающего состояния вычисление останавливается.
Машина, разрешающая язык L = {w#w | w ∈ {0, 1}∗ }:
1. Если символ # встречается на ленте менее или более одного раза,
отвергнуть.
2. Пока слева от # встречается символ 0 или 1,
• заменить первый такой символ a на × и проверить, что первый символ b справа от # совпадает с a; отвергнуть, если не
совпадает или если справа не осталось символов 0 и 1;
• заменить этот символ b на ×.
3. Если справа от # остался символ 0 или 1, отвергнуть; в противном
случае, допустить.
Определение 3. Пусть C1 и C2 — конфигурации машины M . Говорим,
что C1 переходит в C2 , если C2 — это конфигурация машины M после
выполнения одного шага из конфигурации C1 .
3
Например, если
δ(q1 , b) = (q2 , c, L),
то aaq1 bb переходит в aq2 acb. Если
δ(q1 , a) = (q2 , c, R),
то cabq1 a переходит в cabcq2 ␣.
Определение 4. Пусть w ∈ Σ∗ и M — машина Тьюринга с входным
алфавитом Σ. M допускает w, если существует последовательность конфигураций C0 , C1 , . . . , Ck , такая что
• C0 = q0 w;
• Ci переходит в Ci+1 для всех i = 0, . . . , k − 1;
• Ck содержит допускающее состояние qaccept .
n
Псевдокод машины Тьюринга, разрешающей язык {02 | n ≥ 0}:
1. Пройтись слева направо, вычеркивая каждый второй 0.
• Если оказалось, что на ленте только один символ 0, допустить.
• Если оказалось, что на ленте нечетное число символов 0 (но
более одного), отвергнуть.
2. Установить головку на первый входной символ.
3. Повторить.
После каждого прохода по ленте количество символов 0 уменьшается
вдвое.
Теорема 2. Любая многоленточная машина Тьюринга может быть
преобразована в эквивалентную одноленточную машину.
Машины Тьюринга можно закодировать при помощи битовых строк:
0n 10m 10k 10s 10t 10r 10u 1 . . .
• n состояний;
4
• m символов рабочего алфавита;
• k первых символов из них образуют входной алфавит;
• s — номер начального состояния;
• t — номер допускающего состояния;
• r — номер отвергающего состояния;
• u — номер символа пробела;
• правила:
(p, i)(q, j, L) = 0p 10i 10q 10j 10
(p, i)(q, j, R) = 0p 10i 10q 10j 100
Аналогично при помощи битовых строк можно закодировать детерминированные и недетерминированные конечные автоматы, а также строки w ∈ Σ∗ .
Обозначим за bΣ (x) двоичную строку, кодирующую x ∈ Σ∗ . Если
x, y ∈ Σ∗ , назовем парой x и y двоичную строку
(x, y) := 0|x| 1bΣ (x)bΣ (y).
Определим следующие языки над алфавитом {0, 1}:
ADFA = {(B, w) | B — код детерминированного автомата над некоторым
∗
алфавитом Σ, допускающего b−1
Σ (w) ∈ Σ }
ANDFA = {(B, w) | B — код недетерминированного автомата, допускающего b−1
Σ (w)}
ATM = {(C, w) | C — код машины Тьюринга, допускающей b−1
Σ (w)}
Теорема 3 (Универсальная машина Тьюринга). Существует машина
Тьюринга U , получающая на вход
• код произвольной машины Тьюринга M
• и входную строку w
5
и допускающая (M, w) в том и только том случае, если машина M
допускает w.
Это фундаментальное свойство машин Тьюринга: существует машина, которая может выполнять код произвольной машины.
Ни детерминированные, ни недетерминированные конечные автоматы таким свойством не обладают. Другими словами, языки ADFA и ANDFA
не являются регулярными.
Существуют языки, не распознаваемые по Тьюрингу:
1. Существует инъективное отображение множества языков, распознаваемых по Тьюрингу, во множество машин Тьюринга.
2. Существует инъективное отображение множества машин Тьюринга
в {0, 1}∗ .
3. Поэтому существует инъективное отображение множества языков,
распознаваемых по Тьюрингу, в {0, 1}∗ .
4. Но существует биекция между множеством всех возможных языков и множеством всех подмножеств {0, 1}∗ .
5. Множество подмножеств любого множества A содержит больше
элементов, чем A; поэтому должны существовать языки, не распознаваемые по Тьюрингу.
Далее мы поговорим о неразрешимых языках и задачах, для решения
которых не существует алгоритмов.
6
Документ
Категория
Информатика и программирование
Просмотров
55
Размер файла
215 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа