Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

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

leave a comment »

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

Машиною Тюрінга з формальної точки зору є впорядкований набір таких елементів:

  • Q – скінченна множина внутрішніх станів
  • T – скінченний алфавіт символів стрічки. Туди обов’язково має входити символ порожньої клітки — „λ”
  • δ:QxT→QxTx{R,L,ε} однозначна функція переходу.
  • q0∈Q початковий стан.
  • q*∈Q кінцевий стан.

Функція переходу задається множиною записів такого вигляду: pa→qbL, pa→qbR або pa→qb, де p,q∈Q, a,b∈T. Це означає: якщо ми знаходимося в стані p, і читаємо символ a, то переходимо до стану q, записуємо на місці a b, і зміщуємося наліво (L), направо (R), чи залишаємося на місці.

Зазвичай початковим станом q0, вважають такий стан, коли всі символи зліва від головки порожні (λ), а головка показує перший непорожній символ вхідного слова.

При переході до фінального стану q* машина зупиняється.

МТ-обчислювана функція — функція, яку можна обчислити за допомогою машини Тюрінга.

Розглянемо МТ—обчислювані функції над числами в одиничній системі числення. Аргументи будемо розділювати символом дієз (#)

Додавання f(x,y)=x+y

q01→q01R
q0#→q01R
q0λ→q1λL
q11→q*λ

Машина спочатку проходить всі символи зліва направо, замінюючи роздільник на 1. Коли дійшла до кінця (порожнього символа), вертається і стирає зайву одиничку.

Урізана різниця f(x,y)=x-y, якщо x>y, і 0, якщо x≤y

q0#→q4λR
q01→q1λR
q11→q11R
q1#→q1#R
q1λ→q2λL
q21→q3λL
q2#→q*1
q31→q31L
q3#→q3#L
q3λ→q3λR
q41→q4λR
q4λ→q*λ

Віднімання трохи складніше. Ми видаляємо по одній одиничці зліва і зправа, поки, не витремо всі одинички зправа. Якщо залишились тільки праві одинички, це значить, що x<y, і результат нуль. Тоді машина переходить в стан q4, і стирає все. В стані q0 витираємо ліву одиничку, q1 — рухаємося вправо, q2 — витираємо праву одиничку, q3 — рухаємося вліво. Варто зауважити, що ми спочатку витерли ліву, одиничку, і коли при спробі витерти праву, ми виявляємо що її вже немає, то кількість одиничок на стрічці менша на одиницю від потрібної. Тому перехід в кінцевий стан супроводжується додаванням одинички.

А той хто знайде алгоритм добутку з поясненням його роботи — молодець. Я пробував розібратись в тому що в методичці Шкільняка С.С. але виявив там помилку. Також стаття частково за мотивами лекцій.

Advertisements

Written by bunyk

Березень 17, 2009 at 00:39

Оприлюднено в Всяке

Tagged with ,

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: