Алгоритмическая универсальность кинетической машины Кирдина

/

.

. . .

,

,

, 1998. 205 .

. . !

" #

!

,

$

660036, -36, % " # , E-mail: [email protected] – (

). .

, ! .

" #

# $

$ . &

. % ,

!#

$

!

! !

! ,

1&3 1. ( 2. %

$ .

,

' !

, 1&2

.

v ' aba, . . # . , , # ababa, . . !v ' ! . 3. % , ! , # ababa, . . !v ' ! . $ , $ , $ # . $ , , $ ! . $ , ! ! . % , . )! ! $ $ . & , !# : 1. " # $ . 2. * + $ 0. 3. & $ . 4. ) . 5. , $ . - $ , , ' $ , # !$ . % . ! ! " # $ # . " , !# ' ! ! . " !# ! # $ (&- ). . # ! $ !# ! , ! ! ! /0 -" # $ , $ , # , ' ! $ , ' " # $ . http://neuroschool.narod.ru

/ ) & 1) !

' #

! $

.

. . .

"

&- .

'

2)

, $ λ; !

! #

!

, 1998. 205 .

' Q={q1,...,qn}. ) qz; , ' A={a1,...,am}. % !

,

#

q1

3)

,

: !

!#

'

,

$

,

' , '

,

!

,

!

! !

; # $ ! !# aj’,

, !

# qi

$

) qi’; ) !' aj ) $ $ dk, R=Right, E=Equal). 1 !# $! # " # $ ! , α1– $ $ , ! . % , , $ , ' P→Q P→⋅Q ! (

$

# ,

!

$

. aj

: !'

!; D={L,R,E} (L=Left, qiaj→qi’aj’dk. α1qiα2, $ qi– !

#

, , α2– $ ,

,

,

α1

!$ $ . 2 (

# )

α2 ! Q— ' !

.

P1→(⋅)Q1 P2 →(⋅)Q2 Pr →(⋅)Qr $

!

3

' $

'

(

!

) '

$ .& #m #m # ' !

U, V,

!# #. ) #. ! ! R1. 2

R1 –

$

Ri, ! .%

!

$ !

, )

http://neuroschool.narod.ru

Q=UTV. !# $ ! ! ,

!# $

$

.

.

!

Q, .

!

! ! Qm

$ #m→(⋅)Qm – #, .2 P1,...,Pr Ri, . ' , $ , $ ,

, Ri

- $ !

,

!# # !#,

#m→(⋅)Qm $ ' #m→(⋅)Qm – $ , R1

$ . 2

$

!

! P. (

/

.

. . .

,

. *

,

, 1998. 205 .

&

(

+ ) ,

!

' 0. "

! ,

!

,(

'-

! . !# !#

+

, * ) $ .

" #

,

.

,

!

" #

.

!

!

! L=A∪Q. &

(

!# ,

$

' ! .$ , " # $ M0={ q0α }, $ , !#

' &

! !

!

!

$! " # " # $ ,

α∈- . *

$ ––

. "

qiaj→qi’aj’R

uqiajw→uaj’qi’w uaj’qi’→u aj’qi’λ

qiaj→qi’aj’L

ua1qiajw→uqi’a1aj’w ... uamqiajw→uqi’amaj’w qiajw→qi’λaj’w

qiaj→qi’aj’E $

uqiajw→uqi’aj’w

! .

" # uvw→usw

, %

λ→⋅λ, $ λ ! " # $ , - $ )

# ( ) & %

!

. !

. 2 !!

# # ' &

, . v→s. % ."

$

!

, (

)

!

,

, '

,

#

'

.

!. " ! ?%

,

!

, ./ .

$

,

. /

!#

' , !

$ " # $ . ! ! 4

! ! ! ,

! .

" # $

'

– $ ,

. '

$ # –

. $!

!

! uf,

$! ,

$ http://neuroschool.narod.ru

. .

$ $!

", ! gw. $ !

/ uk

qw. 2 !

.

. . . ! #

$! “

,

,

,

!# !$ $ ! ”

$! usw.

'

“ (i- ) ”. )

ri - “

'

. % #

, '

”).

#

,

$

, ! ,

(

, 1998. 205 .

: ∆t # ri∆t # 1-Σiri∆t - ! ( $ ' (o(∆t)). 2 ! # .2 ! !# ! ∆t, ' !# ! ∆t. % ∆t→0 !# .

!

#

' ,

-

!

); i-

-

,

, !

,

, !

!

-

%

: ! ' $

$

!

56 ($

, . "4&"2* -647" ( 7F0113).

#

# 8 68,

. 2.1.)

-.&. 4

1. &

' . " V % , *"3, 1997. ).101. 2. * ! 2... $ // " . ." $ $ $ ! (4& 4 – 98). – & : , 1998. – C.77. 3. -.-., & $ &. . " $ .– .: & ! . * . 1984. 4. 3 %.-., ) -.9. " $ : ' .– .: & ! . * . . .. ., 1987.– (,$

http://neuroschool.narod.ru

// . –

.

.

4 .-

).

! .

.,