Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v11(1-4)/letunovskiy-769-772.pdf Дата изменения: Mon Feb 18 14:24:16 2008 Дата индексирования: Tue Oct 2 00:33:00 2012 Кодировка: Поисковые слова: m 5

. .
. , , , . .
n Ek = {0, 1, . . . , k - 1}, g : Ek Ek k - , a(1)a(2) . . . , Pk . Ek a(j ) Ek , j = 1, 2, . . . . N . f : (Ek )n (Ek )m

(a-), (1) q1 (1) = q 01 , ... q (1) = q 0 s s q1 (t + 1) = 1 (q1 (t), . . . , qs (t), a1 , . . . , an ), (1) ... qs (t + 1) = s (q1 (t), . . . , qs (t), a1 , . . . , an ) b1 (t) = 1 (q1 (t), . . . , qs (t), a1 , . . . , an ) ... bm (t) = m (q1 (t), . . . , qs (t), a1 , . . . , an )


770

. .

q = (q1 , . . . , qs ) a- f , q 0 , a = (a1 , a2 . . . , an ) b = (b1 , . . . , bm ) , a(1)a(2) . . . b(1)b(2) . . . c, . - , ,
n s m (Ek , Ek , Ek , , , q 0)

, f . (A, Q, B , , , q 0), n s m A Ek , Q Ek , B Ek . : (q , a(1), . . . , a(t)) = ( . . . (q , a(1), . . . , a(t - 1)), a(t)), (q , a(1), . . . , a(t)) = ((q , a(1), . . . , a(t - 1)), a(t)) (q , a(1), . . . , a(t)) = (q , a(1), . . . , a(t-1)) ((q , a(1), . . . , a(t-1)), a(t)). a- P . . [5]. ( f )(x1 , x2 , . . . , (f )(x1 , x2 , . . . , ( f )(x1 , x2 , . . . ( f )(x1 , x2 , . . . , (f g )(x1 , x2 , . . xn ) = f (x2 , x3 , xn ) = f (x2 , x1 , , xn ) = f (x1 , x1 xn ) = f (x2 , x3 , . , xm+n-1 ) = f . . . , xn , x1 ), x3 , . . . , x n ) , . . . , xn-1 ) . . . , xn+1 ) (g (x1 , . . . , xm ), x

m+1

,...,x

m+n-1

)

M P , [M ] a-, M . G0 , q (1) = 0, q (t + 1) = a(t), b(t) = q (t), . P .
(1)

-




771

, q (t + 1) = (t). K . : M K , [M {G0 , P
(1)

}].

1. M , , [M {G0 , P (1) }]. . . . . . .


[1] . . , // . . 151. 3. 1963. C. 493­496. [2] . . // . 1964. . 155. 1. . 35­37. [3] . . // . . 4. . 4. . 41­56. .: , 1992. [4] . . - // . 4. . 367. 1999. . 439­441. [5] . . // . 1966. . 5. 2. C. 5­24. [6] . ., . ., . . . .: , 1985. [7] . . // . . 9. . 1­4. 2005. . 457­469.