Участник:Qwerty/количество машин тьюринга

Материал из DISCOPAL
Перейти к: навигация, поиск


Из одного состояния по i символу можно перейти m+1 способами

(можем остаться на месте). Всего символов n+1. Значит, для данного

		 	

состояния необходимо задать по одному переходу через каждый символ - (m+1)^(n+1). 

− столько же будет для всех остальных состояний, которых m+1 - (m+1)^(n+1)*...*(m+1)^(n+1)= (m+1)^((m+1)(n+1))

(две машины отличаются, если хотя бы в 1 состоянии по хотя бы 1 символу разный переход)



StasFomin (обсуждение) 06:54, 30 марта 2017 (UTC): Ну, это тоже самое, что Участник:Qwerty/Задача о количестве машин тьюринга