Виберіть індивідуальне завдання відповідно варіанту.
Завдання 1. Доведіть що задана функція обчислювана по Т’юрингу, для чого побудуйте машину Т’юринга яка її обчислює.
№ варіанту
| Завдання 1
| Завдання 2
|
1.
| f (x, y) = x + y.
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
2.
| , початковий стан на нулику зліва від одиниць, кінцевий стан на тій же комірці, що й початковий, наприклад:
q10 1x 0=> q0000.
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
3.
| f (x) = x +2.
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
4.
| , початковий стан на нулику зліва від одиниць, кінцевий стан на тій же комірці, що й початковий, наприклад:
q101x 0=> q0010
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
5.
|
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
6.
| .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
7.
| f (x, y) = x – y (x ≥ y).
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
8.
|
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
9.
| - ціла частина
числа .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
10.
| .
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
11.
| .
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
12.
| .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
13.
|
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
14.
| .
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
15.
| .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
16.
|
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
17.
|
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
18.
|
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
19.
|
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
20.
| f (x, y) = x – y (x ≥ y)
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
21.
| - ціла частина
числа .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
22.
| .
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
23.
|
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
24.
| .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
25.
|
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
26.
| , початковий стан на нулику зліва від одиниць, кінцевий стан на тій же комірці, що й початковий, наприклад:
q10 1x 0=> q0000.
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
27.
| .
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|
28.
|
| Побудувати машину Т'юринга яка називається "транспозицією" і позначається В, та здійснює переведення 01 xq 101 y 0 01 yq 001 x 0.
|
29.
|
| Побудувати машину Т'юринга яка називається "подвоєння" і позначається Г, та здійснює переведення q 101 x 0 q 001 x 01 x 0.
|
30.
|
| Побудуйте машину Т'юринга яка називається "Перенесення нуля" і
позначається А, що здійснює переведення слова q 1001 x 10 q 001 х 00.
|