Головна

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

  1.  БЕЗПЕКА РОБОТИ НА ПЕРСОНАЛЬНИХ електронно-обчислювальних МАШИНАХ
  2.  Де йдеться про рахункових машинах і про касах, які вміють захищатися
  3.  Глава 14. Машина виявлення
  4.  Глава 5. Алгоритми і машина Тьюринга.
  5.  Двомірна схема течії газу в лопаткових машинах.
  6.  дерьмовое МАШИНА
  7.  Якщо немає товарної позиції, конкретно описує цю частину, визначається машина, з якої така частина головним чином використовується.

Доказ алгоритмічної нерозв'язності певних завдань стало можливим після уточнення поняття алгоритму. У першій половині 20 століття було запропоновано кілька таких уточнень, згодом опинилися еквівалентними. Всі вони виходять з того, що алгоритм можна розглядати як відображення з безлічі описів завдань у безліч результатів. Якщо елементи цих множин закодувати цілими невід'ємними числами, то алгоритмічний процес являє собою обчислення деякої функції, аргументи і значення якої є цілими невід'ємними числами. Функція називається обчислюваною, якщо її значення можуть бути обчислені за допомогою алгоритму. Тоді існування невичіслімих функцій тягне існування алгоритмічно нерозв'язних завдань.

У 30 - х роках англійським математиком Тьюрингом в якості моделі алгоритму було запропоновано гіпотетичне обчислювальний пристрій, який в певній мірі виявилося прототипом сучасних ЕОМ. Тепер його називають машиною Тьюринга (МТ).

МТ маємо кінцеве безліч внутрішніх станів Q = {q0, q1 , ..., Qm}, Де q1 вважається початковим, а q0 - Кінцевим станами, а також зовнішню пам'ять у вигляді стрічки, що складається з кінцевого числа осередків, в яких записані символи з зовнішнього алфавіту A = {a0, a1, ..., an}, Причому символ a0 вважається порожнім і зазвичай позначається як 0. У процесі роботи МТ до існуючих осередків можуть прилаштовуватися нові порожні клітинки, так що стрічка є потенційно необмеженої в обидві сторони.

У кожен з дискретних моментів часу МТ знаходиться в одному зі своїх внутрішніх станів і оглядає одну з комірок стрічки, сприймаючи записаний в ній символ. Залежно від внутрішнього стану і сприйманого символу в наступний момент МТ переходить в нове внутрішній стан (можливо, те ж саме), записує новий символ в оглядається осередок (можливо, той же самий) і починає оглядати сусіднього осередок ліворуч, або ту ж саму осередок , або сусіднього осередок праворуч. Таким чином, функціонування МТ задається трьома функціями:

G: Q  A ® Q

F: Q  A ® A

D: Q  A ® {L, C, R}.

Потрапивши в заключне стан q0, МТ припиняє роботу.

Функції G, F, і D задаються набором команд або програмою для МТ. Команди мають вигляд qi aj ® qk al sp, Де qk = G (qi aj), Ai = F (qi aj), Sp = D (qi, aj).

У кожен момент часу стан МТ повністю визначається внутрішнім станом qi, Вмістом осередків стрічки ai1, ai2 , ..., Ait і номером k оглядається осередку, що в сукупності називається конфігурацією і може бути записано як ai1 ai2 , ..., Aik-1

qi aik aik + 1 ... ait.

Конфігурацій, що виходять з даної приписуванням зліва чи справа довільного числа порожніх клітинок, вважаються еквівалентними. В процесі роботи МТ відбувається послідовна зміна конфігурацій. Початкова конфігурація повинна бути задана. Тоді всі наступні конфігурації визначаються програмою. Якщо домовитися вважати, що в початковий момент машина знаходиться в стані q1 і оглядає найлівішу осередок стрічки, то початкова конфігурація повністю задається початковим словом - набором записаних в осередках стрічки символів.

Почавши роботу з деякого початкового слова, МТ або зупиниться через кінцеве число кроків, або ніколи не зупиниться. У першому випадку говорять, що МТ застосовна до слова Р, а в другому, - що не може бути застосована.

Перейдемо до розгляду прикладів. Будемо використовувати зовнішній алфавіт з двох символів A = {0, 1}. Якщо Р - деяке слово, то для слова P P ... P (m раз) будемо для стислості використовувати позначення [P]m. Так, наприклад, слово 1100011000111 запишеться як [12 03]2 13.

Нехай МТ з трьома внутрішніми станами q0, q1 і q2 задається програмою:

q1 0 ® q1 0R

q1 1 ® q2 0R

q2 1 ® q1 0R

q2 0 ® q0 1C.

Нехай початкове слово P = 13 01. Тоді при роботі МТ послідовно виникають конфігурації: q1 13 01, q2 12 01, q1 101, q2 01, q0 12.

МТ зупинилася, перейшовши в заключне стан q0, тобто МТ застосовна до даного слова.

Нехай тепер початкове слово p = 14. Тоді послідовними конфігураціями будуть:

q1 14, q2 13, q1 12, q2 1, q1 0, q1 0, q1 0, ...

МТ ніколи не зупиниться, тобто МТ не може бути застосована до даного слова.

Нехай тепер потрібно побудувати МТ, додають до даного неотрицательна цілому числу одиницю, тобто МТ повинна переводити конфігурацію q1 1n в q0 1n+1. Ось така МТ:

q1 1 q1 1 R

q1 0 q2 1 L

q2 1 q2 1 L

q2 0 q0 0 R.

Нехай тепер потрібно вирішити задачу подвоєння числа, тобто q1 1n ® q0 12n. Це завдання може бути вирішена за допомогою такої МТ:

q1 1 ® q2 0R

q2 1 ® q3 1 L

q3 0 ® q4 0 L

q4 1 ® q4 1 L

q4 0 ® q5 1R

q5 1 ® q5 1R

q5 0 ® q1 1R

q2 0 ® q6 1 L

q6 1 ® q6 1 L

q6 0 ® q0 1C.

Ідея алгоритму полягає в тому, що в заданому слові 1n вводиться маркерний 0, який в ході роботи алгоритму пересувається зліва направо. При кожному його пересуванні зліва до слова приписується 1. МТ завершує роботу, коли маркерний 0 досягає правого кінця вихідного слова.

 Глава 5. Алгоритми і машина Тьюринга. |  Алгоритмічно нерозв'язні проблеми.


 Алгебраїчні структури і морфізм. |  тест II |  Визначення та основні властивості. |  Диз'юнктивна і Кон'юнктивна нормальні форми |  Спрощення д.н.ф. |  тест III |  Обчислення висловлювань. |  логічний наслідок |  Предикати і квантори |  Тест IV. |

© 2016-2022  um.co.ua - учбові матеріали та реферати