Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется

Если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, машина Тьюринга называется

Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является

При любом входе машина Тьюринга должна

Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется

Если в задаче нет полинома длины, который сверху ограничивал функцию максимума, то такая задача называется

Существует ли полиноминально точный алгоритм решения оптимизационной задачи многопроцессорного расписания?

Если существует NP-полная задача П₁, которая сводится по Тьюрингу к задаче П₂, то задача П₂ является

Подмножество вершин графа, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством, носит название

Пара узлов графа носит название

Для какого состояния машины Тьюринга не формируются правила