Изменения
→Многомерный квантовый конечный автомат
===Многомерный квантовый конечный автомат===
Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
<math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math>- допускающее пр-во , <math> \mathcal{H}_r </math> - отвергающее пр-во , <math> \mathcal{H}_{non} </math> - промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
