Оглавление
- 1 Решающий модуль (машина Тьюринга)
- 1.1 Определение и свойства решающих модулей
- 1.2 Неразрешимость определения решающего модуля
- 1.3 Примеры функций, вычисляемых решающими модулями
- 1.4 Связь с частичными машинами Тьюринга
- 1.5 Невозможность создания полной модели вычислений
- 1.6 Проблема принятия решений о полной остановке
- 1.7 Доказуемость полной остановки машины Тьюринга
- 1.8 Примеры машин Тьюринга, которые не могут быть доказаны
- 2 Решатель (машина Тьюринга) — Википедия
Решающий модуль (машина Тьюринга)
-
Определение и свойства решающих модулей
- Решающий модуль — это машина Тьюринга, которая останавливается на каждом входе.
- Решающий модуль также известен как полная машина Тьюринга.
- Решающие модули могут определить, является ли строка членом рекурсивного языка.
-
Неразрешимость определения решающего модуля
- Определение того, является ли машина Тьюринга решающей, является неразрешимой задачей.
- Проблема остановки является частным случаем этой задачи.
-
Примеры функций, вычисляемых решающими модулями
- Решающие модули могут вычислять функции, которые всегда останавливаются, даже если они ограничены памятью.
- Пример — конечное дерево решений.
- Некоторые функции, такие как функция Аккермана, могут быть вычислены с помощью решающих модулей.
-
Связь с частичными машинами Тьюринга
- Решающие модули не включают в себя все частично вычислимые функции.
- Теорема показывает, что существуют частные функции, которые не могут быть расширены до полных функций.
-
Невозможность создания полной модели вычислений
- Не существует модели вычислений, которая вычисляет только полные функции и вычисляет все полные функции.
- Построение машины Тьюринга, которая имитирует другие машины Тьюринга, приводит к противоречиям.
-
Проблема принятия решений о полной остановке
- Проблема принятия решений о полной остановке машины Тьюринга неразрешима и находится на уровне Π20 из арифметической иерархии.
-
Доказуемость полной остановки машины Тьюринга
- В некоторых системах доказательств каждая доказуемо полная машина Тьюринга действительно является полной.
- В других системах доказательств существуют машины Тьюринга, которые считаются полными, но не могут быть доказаны как таковые.
-
Примеры машин Тьюринга, которые не могут быть доказаны
- Машина Тьюринга, которая проходит через последовательности Гудштейна и останавливается на нуле, является тотальной, но не может быть доказана в арифметике Пеано.
Полный текст статьи: