Машина Тьюринга

Тьюринг у 1936 р. розглянув гіпотетичну „машину”, яка має скінченну множину внутрішніх станів і одну нескінченно велику стрічку, розділену на комірки, яку машина могла пересувати за такт на одну комірку праворуч чи ліворуч. У кожну комірку машина може записати символ із скінченного алфавіту А. Початково стрічка має бути порожньою, за винятком скінченної кількості комірок, які заповнюють завчасно. Ці наперед заповнені комірки можна розуміти як програму запуску машини.

Основні відмінності між машиною Тьюринга та скінченним автоматом полягають в тому, що: 1) стрічка машини Тьюринга нескінченна; 2) машина Тьюринга машина може пересуватися по стрічки (чи зміщувати стрічку) в будь-якому напрямі. Це надає машині нескінченну пам’ять, яку можна використовувати під час обчислень. Кожну комірку можна переглядати багатократно.

Означення. Машиною Тьюринга назвемо п’ятірку {A, S, , , }, де A = (a₀, …, a_n) – скінченний алфавіт символів, які можуть бути записані в комірках і одночасно є вхідними та вихідними; S – скінченна множина внутрішніх станів; S = {s₀, s₁, …, s_r},  – функція з S  A  S;  – функція з S  A в А;  – функція S  A в множину {L, R, STOP}.

Машина Тьюринга працює так. Вона починає роботу, перебуваючи в початкову стану s₀. Після считування першого символу вона переходить у новий внутрішній стан, який визначається функцією . Записує в комірку символ, який є значенням функції . Переміщає стрічку направо (R), наліво (L), чи залишається на місці та закінчує роботу (STOP), залежно від значень функції .

Приклад 1. Нехай задано два слова a₀a₁ й a₂a₃a₄a₅



a0

a1



a2

a3

a4

a5



Завдання полягає в тому, щоб починаючи з лівого кінця стрічки вилучити символи a₃ та a₅, замінивши їх символами a₂ й a₄, після чого певернутися до лівого кінця стрічки. Порожню комірку позначимо .

Послідовні конфігурації розв’язування сформульованої задачі мають такий вигляд

q₀a₀a₁a₂a₃a₄a₅  a₀q₀a₁a₂a₃a₄a₅  a₀a₁q₀a₂a₃a₄a₅ 

 a₀a₁ q₁a₂a₃a₄a₅  a₀a₁a₂q₂a₃a₄a₅  a₀a₁a₂q₂a₂a₄a₅ 

 a₀a₁a₂a₂q₂a₄a₅  a₀a₁a₂a₂a₄q₂a₅  a₀a₁a₂a₂q₃a₄a₄ 

 a₀a₁a₂q₃a₂a₄a₄  a₀a₁q₃a₂a₂a₄a₄  a₀a₁q₃a₂a₂a₄a₄ 

 a₀q₃a₁a₂a₂a₄a₄  q₃a₀a₁a₂a₂a₄a₄.

Тема „Основні поняття і властивості алгоритмів”

Алгоритм – це ефективна процедура, яка однозначно приводить до результату. Наприклад, метод Гаусса розв’язання систем лінійних рівнянь, правило диференціювання складеної функції, добування квадратного кореня з раціонального числа із заданою мірою точності тощо.

Основні вимоги до алгоритмів

1. Будь-який алгоритм застосовується до початкових даних і видає результат. У технічних термінах це означає, що алгоритм має входи і виходи. Крім того, під час роботи алгоритму з’являються проміжні результати, що використовуються далі. Таким чином, кожний алгоритм використовує дані початкові, проміжні та вихідні.

2. Дані для свого розміщення потребують пам’яті. Пам’ять вважається однорідною і дискретною, тобто складається з однакових комірок, причому кожна комірка може містити один символ алфавіту даних.

3. За виконавця алгоритму можуть виступати людина, різні технічні пристрої, наприклад, робот або ЕОМ. У будь-якому випадку має бути досягнута визначена мета, інакше вся послідовність дій втрачає сенс.