Докво основано на сведение “Проблемы остановки” к “Проблеме самоприменимости”
3. Меры вычислительной сложности алгоритмов.
4. Построение машины Тьюринга, распознающей симметрию.
Состоя |
0 |
1 |
|
Комментарий |
ние |
|
|
|
|
|
|
|
|
|
q1 |
Rq2 |
Rq3 |
1Sq0 |
запоминаем самый левый |
|
|
|
|
символ |
|
|
|
|
|
q2 |
0Rq2 |
1Rq2 |
Lq4 |
гоним головку вправо для |
|
|
|
|
последующего сравнения |
|
|
|
|
с 0 |
|
|
|
|
|
q3 |
0Rq3 |
1Rq3 |
Lq5 |
гоним головку вправо для |
|
|
|
|
последующего сравнения |
|
|
|
|
с 1 |
|
|
|
|
|
q4 |
Lq7 |
Lq6 |
1Sq0 |
сравниваем самого |
|
|
(слова не |
|
правого с 0 |
|
|
симметри |
|
|
|
|
чно) |
|
|
|
|
|
|
|
q5 |
Lq6 |
Lq7 |
1Sq0 |
сравниваем самого |
|
|
|
|
правого с 1 |
|
|
|
|
|
q6 |
Lq6 |
Lq6 |
Rq0 |
затираем все символы |
|
|
|
|
|
q7 |
0Lq2 |
1Lq7 |
Rq1 |
гоним головку влево |
|
|
|
|
|
5. Метод следов для получения нижних оценок сложности.
6. Моделирование многоленточных машин Тьюринга одноленточными.
8. Теорема Цейтина о существовании сложновычислимых функций.
9. Теорема Рабина о существовании сложновычислимых функций.
Для любой вычислимой функции h(n) существует функция, принимающая два значения 0 и 1, такие что для любой машины Тьюринга М, вычисляющую функцию f(n), существует значение n0 , что x, x ≥ n, tM(x) > h(x)
10. Связь между различными характеристиками сложности.
11. Аксиомы Блюма. Общий подход к понятию сложности вычислений.
Аксиомы Блюма— это аксиомы, которые определяют свойства мер сложности на множестве вычислимых функций. Впервые эти аксиомыбыли сформулированы Мануэлем Блюмом в 1967 году.
Важным является тот факт, что и теорема Блюма об ускорении, и теорема о промежутке верны для любых мер сложности, удовлетворяющих этим аксиомам. Наиболее известными примерами таких мер являются время выполнения (TIME) и объем используемой памяти (SPACE).
12. Класс P. Полиномиальная сводимость. Элементарные свойства полиномиальной сводимости.
13. Недетерминированные машины Тьюринга.