Эта публикация цитируется в 20 статьях

Разрешимость проблемы остановки для некоторых классов машин Тьюринга

Л. М. Павлоцкая

Московский энергетический институт

Аннотация: Один из способов доказательства неуниверсальности некоторой машины Тьюринга состоит в доказательстве разрешимости для нее проблемы остановки. Поэтому для получения нижней оценки сложности универсальной машины удобно иметь критерии разрешимости проблемы остановки. В настоящей работе устанавливаются некоторые из таких критериев; они формулируются в терминах свойств машинных графов и вычислений. Библ. 4 назв.

УДК: 519.9

Поступило: 01.11.1972

 Англоязычная версия: Mathematical Notes, 1973, 13:6, 537–541

Реферативные базы данных:

• 
•