Математическая логика и теория алгоритмов. Сергиевская И.М. - 55 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

Составители: 

Рубрика: 

60
1)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Rqq
Eqq
Lqq
Rqq
T
11
00
11
00
:
12
02
21
11
; а) 011
3
=P ; б) 101
=
P
.
2)
⎪
⎩
⎪
⎨
⎧
Rqq
Rqq
Rqq
T
11
01
00
:
12
21
21
; а)
3
1=
P
; б) 110
2
=P .
3)
⎪
⎪
⎩
⎪
⎪
⎨
⎧
Eqq
Lqq
Lqq
Lqq
T
11
10
01
10
:
02
12
21
11
; а)
110
2
=
P
; б)
222
101
=
P
.
4)
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
Rqq
Lqq
Rqq
Lqq
Rqq
T
00
01
10
01
10
:
13
32
32
11
21
; а)
110
3
=
P
; б)
[
]
110
2
=P .
5)
⎪
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎪
⎨
⎧
Lqq
Eqq
Lqq
Rqq
Rqq
Rqq
T
01
10
01
00
11
10
:
03
23
12
32
21
21
; а)
2
1=
P
; б)
110
4
=
P
.
3. Построить в алфавите {0,1} машину Тьюринга, обладающую свойствами:
1)
машина имеет одно состояние, одну команду и применима к любому слову в
алфавите {0,1};
2)
машина имеет одно состояние, две команды, не применима ни к какому слову в
алфавите {0,1}, и в процессе работы головка обозревает бесконечное множество
ячеек;
3)
машина имеет две команды, не применима ни к какому слову в алфавите {0,1}, и
в процессе работы головка обозревает одну ячейку.
Предполагается, что в начальный момент времени головка машины обозревает
самый левый символ слова.
4. По словесному описанию машины Тьюринга построить ее программу (в
алфавите {0,1}). 
         ⎧q1 0q1 0 R
         ⎪q 1q 1L
         ⎪ 1 2
1)   T :⎨                 ; а) P = 1301 ; б) P = 101.
         ⎪q 2 0 q 0 0 E
         ⎪⎩q 2 1q11R
          ⎧q1 0q2 0 R
          ⎪
2)   T : ⎨q11q2 0 R ; а) P = 13 ; б) P = 10 21 .
          ⎪q 1q 1R
          ⎩ 2 1
          ⎧q1 0q11L
          ⎪q 1q 0 L
          ⎪ 1 2
3)   T :⎨                ; а) P = 10 21 ; б) P = 12 0 212 .
          ⎪q 2 0q11L
          ⎪⎩q 2 1q01E
            ⎧q1 0q2 1R
            ⎪q 1q 0 L
            ⎪⎪ 1 1
      T : ⎨q2 0q31R ; а) P = 1031 ; б) P = [10] 1 .
                                                        2
4)
             ⎪q 1q 0 L
             ⎪ 2 3
             ⎪⎩q3 0q1 0 R
       ⎧q1 0q 2 1R
       ⎪q 1q 1R
       ⎪ 1 2
       ⎪⎪q 2 0q3 0 R
5) T : ⎨             ; а) P = 12 ; б) P = 10 41 .
        ⎪q 2 1q1 0 L
        ⎪q3 0q 2 1E
        ⎪
        ⎪⎩q31q0 0 L

      3. Построить в алфавите {0,1} машину Тьюринга, обладающую свойствами:
1) машина имеет одно состояние, одну команду и применима к любому слову в
   алфавите {0,1};
2) машина имеет одно состояние, две команды, не применима ни к какому слову в
   алфавите {0,1}, и в процессе работы головка обозревает бесконечное множество
   ячеек;
3) машина имеет две команды, не применима ни к какому слову в алфавите {0,1}, и
   в процессе работы головка обозревает одну ячейку.
      Предполагается, что в начальный момент времени головка машины обозревает
самый левый символ слова.

     4. По словесному описанию машины Тьюринга построить ее программу (в
алфавите {0,1}).




                                                          60

Страницы