Заключение. 
Проблема остановки машины Тьюринга

В настоящей работе получены достаточные условия разрешимости проблемы остановки (п.о.) машин Тьюринга. Эти условия сформулированы в терминах свойств машинных программ. С их помощью доказывается разрешимость п.о. для машин Тьюринга с двумя символами и не более чем тремя состояниями.

Мы показали, что для установления разрешимости п. о. на всем множестве начальных конфигураций достаточно исследовать лишь подмножество «граничных» конфигураций. С использованием этого факта были доказаны достаточные условия разрешимости п. о.

Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга (в которую введены конкретные начальные данные) или нет. Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи.

Список литературы

• 1. Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание. — М.: Техносфера, 2004. — с. 310−317.
• 2. Плотников А. Д. Дискретная математика: учеб. пособие / А. Д. Плотников. — М.: Новое издание, 2005. — 288 с.
• 3. Фалевич Б. Я. Теория алгоритмов. — М.: ИНФРА-М, 2006. — с. 324.
• 4. Фалина Н. М. Машина Тьюринга // Информатика. — № 26. — 2005.
• — с.12−15.
• 5. Свободная энциклопедия — [Электронный ресурс]. Режим доступа: http://ru.psyphy.wikia.com/wiki/15.
• 6. Учебный контент — [Электронный ресурс]. Режим доступа: http://ref.rushkolnik.ru/v62794/?page=4
• 7. Павлоцкая Л. М. О машинах Тьюринга, связных относительно свойства неразрешимости проблемы остановки. //Матем. заметки, 71:5 (2002).
• — с. 732−741.
• 8. Кацарин Т. К, Строева Л. Н. Машины Тьюринга и рекурсивные функции: учеб. пособие / изд.-полиграф. центр, Воронежский гос. университет, 2008. — с. 5−17.