ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Композиція машин Т'юринга.

Визначення.Нехай задані машини Т'юринга Θ₁ і Θ₂, що мають загальний зовнішній алфавіт {a₀, a₁, …, a_m} і алфавіти внутрішніх станів {q₀, q₁, …, q_n}і відповідно. Композицією (чи множенням) машини Θ₁ на машину Θ₂ називається нова машина Θ з тим же зовнішнім алфавітом {a₀, a₁, …, a_m}, внутрішнім алфавітом {q₀, q₁, …, q_n, q_n₊₁, …, q_n_+t} і програмою, що виходить наступним чином. У всіх командах з Θ₂ що містять символ q₀, залишаємо незмінними, а всі останні стани на , змінюємо відповідно на q_n_+i. Сукупність усіх так отриманих команд утворює програму машини-композиції Θ.

Введене поняття є зручним інструментом для конструювання машин Т'юринга. Покажемо це на прикладі.

Приклад 6. Сконструюємо машини Т'юринга, правильно обчислюючі функції-проектори .

Розглянемо спочатку конкретний випадок n = 3, m = 2, тобто функцію . Ми повинні переробити слово в слово . Будемо застосовувати до початкової конфігурації послідовно сконструйовані раніше машини Т'юринга Б+, В, Б^- , О:

Таким чином, функція обчислюється слідуючою композицією машин Б⁺ВБ⁺ОБ^-ОБ^- = Б⁺ВБ⁺(ОБ^-)².

Перевірте самостійно, що функція обчислюється композицією Б⁺ВОБ^-.

Тепер ми можемо уявити собі алгоритм побудови композиції машин Б⁺, В, Б^-, О для обчислення будь-якої функції виду

. За допомогою правого зрушення Б+, застосувавши його т-1 раз, треба спочатку досягти масиву

Потім, рухаючись вліво, транспонувати (за допомогою В) масив з кожним сусіднім ліворуч масивом, поки масив не вийде на перше місце:

Тепер треба дійти до крайнього правого масиву за допомогою (n - 1) -кратного застосування правого зрушення Б+:

Нарешті, треба стирати послідовно справа наліво усі масиви одиниць, окрім першого:

Отже, цю функцію (правильно) обчислює наступна машина Т'юринга: (Б⁺)^m^-1 (В ∙ Б^-)^m^-1(Б⁺)ⁿ^-1(О ∙ Б^-) ⁿ^-1.

При n = 3, m = 2 така машина має вигляд:

Б⁺ВБ^-(Б⁺)²(ОБ^-)² = Б⁺ВБ⁺(ОБ^-)²

тобто співпадає з побудованою вище машиною. При n = 2, m = 2 ця машина має вигляд: Б⁺(ВБ^-)Б⁺(ОБ^-) = Б⁺ВОБ^-, тобто також співпадає з відповідною розглянутою вище машиною Т'юринга.

Приклад 7. Побудуйте машину Т'юринга, що переводить слово 01^x01^y01^z0 в слово 01^z01^x01^y0, причому в початковому положенні оглядається комірка з 0 між наборами з у і z одиниць, а в кінцевому положенні оглядається комірка з 0 між наборами з z і х одиниць. (Ця машина називається "Циклічне зрушення" і позначається Ц.)

Рішення. Перевіримо, що таке переведення станеться в результаті послідовного застосування (композиції) раніше побудованих машин В, Б^- і В.

Обчислюємо:

01^x01^yq₁01^z0

В: 01^x01^zq01^y0

Б^-: 01^xq01^z01^y0

B: 01^zq₀01^x01^y0.

Тобто Ц = ВБ^-В

Приклад 8. Побудуйте машину Т'юринга, що переробляє слово 01^x01^y в слово 01^x01^y01^x01^y, причому в початковому положенні оглядається найлівіша комірка, а в кінцевому - комірка, в якій записаний 0, який знаходиться між масивами 1^x01^y і 1^x01^y. (Машина називається "копіювання" і позначається К₂.)

Рішення. Перевіримо, що таке переведення станеться в результаті послідовного застосування (композиції) раніше побудованих машин.

q₁01^x01^y 01^xq₀01^y01^x01^y

Обчислюємо:

q₁01^x01^y

Б⁺: 01^xq01^y

Г : 01^xq01^y01^y0

Б^-: q01^x01^y01^y0

Г : q01^x01^x01^y01^y0

Б⁺: 01^xq01^x01^y01^y0

Б⁺: 01^x01^xq01^y01^y0

В : 01^x01^yq01^x01^y0

Б^-: 01^xq01^y01^x01^y0

К₂ = Б⁺ГБ^-Г(Б⁺)²ВБ^-.

Індивідуальні завдання.

Виберіть індивідуальне завдання відповідно варіанту.

Завдання 1. Доведіть що задана функція обчислювана по Т’юрингу, для чого побудуйте машину Т’юринга яка її обчислює.

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