МАШИНА ТЮРІНГА

Неформально, Машина Тюрінга (далі МТ) представляє собою автомат з скінченим числом станів і безмежною пам’яттю, яка представлена набором однієї чи більше стрічок, безмежних на обох кінцях. Стрічки поділяються на аналогічно нескінчене число чарунок, і на кожній стрічці виділена стартова (нульова) чарунка. В кожній чарунці може бути записано тільки один символ з деякого скінченого алфавіту Σ, де передбачений символ «*» для позначення пустої чарунки.

На кожній стрічці є головка зчитування-запису, і всі вони під’єднані до «керуючого модуля» МТ — автомату з скінченою множиною станів Γ.

Є виділений стартовий стан (напр., «START») и стан (чи набір станів) завершення (напр. «STOP»). Перед запуском МТ знаходиться в стані «START», а всі головки стоять на нульових чарунках відповідних стрічок. На кожному кроці всі головки зчитують інформацію з своїх поточних чарунок і посилають її керуючому модулю МТ. В залежності від цих символів і стану керуючий модуль робить наступні операції:

  1. Посилає кожній головці символ для запису в поточну чарунку кожної стрічки;
  2. Посилає кожній головці одну з команд «LEFT»,”RIGHT”,”STAY”;
  3. Виконує перехід в новий стан (яке, може збігатись з попереднім).

    Більш формально: Машина Тюрінга це набір , де

    k – натуральне число, Σ,Γ – кінцеві множини вхідного алфавіту і станів відповідно, – символ-пробіл, – виділені стани, α,β,γ мимовільні відображення:

  • (задає новий стан);
  • (задає символи для запису на стрічки);
  • (визначає, як рухати головки).

    Зручно рахувати, що алфавіт Σ містить крім «пробіла» («*») два виділених символа, «0» і «1» (Звичайно обмежуються ).

    Під входом для МТ розуміють набір з k слів (k-кортеж слів з Σ * ), записаних на k стрічках починаючи з нулевих позицій. Звичайно, на вхідні дані записують тільки на першу стрічку, і під входом x розуміють k-кортеж .

    Результатом роботи МТ на деякому вході являється також k-кортеж слів з Σ * , які залишилися на стрічках. Для простоти також зручно рахувати, що результатом є тільки слово на останній стрічці, а всі останні — просто сміття.

    Також рахується, що вхідне слово не містить пробілів — авжеж, тому, що по іншому як побачити, де кінчається вхідне слово (Можливо звісно дозволити пробіли, але тоді прийдеться зарезервувати ще один символ — «кінець вводу»).

    Існують наступні різновиди машини Тюрінга:

  • Недетермінована машина Тюрінга
  • Випадкова машина Тюрінга
завантаження...
WordPress: 22.75MB | MySQL:26 | 0,322sec