Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Машина Тьюрінга
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
Звіт
до лабораторної роботи № 9
з теми: «Машина Тьюрінга»
Львiв 2007
1. МЕТА РОБОТИ
Метою роботи є вивчення машин Тьюрінґа.
2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI
2.4 Машина Тьюрінга
2.4.1 Історія виникнення
Алан Тьюрінг у 1936 році опублікував у працях Лондонського математичного товариства статтю «Про обчислювальні числа у застосуванні до проблеми розв’язуваності», яка разом із роботами Поста і Черча лежить в основі сучасної теорії алгоритмів.
Передісторія створення цієї роботи пов’язана із формулюванням Давидом Гільбертом на Міжнародному математичному конгресі у Парижі у 1900 році нероз’язуваних математичних проблем. Однією з них була задача доведення несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як “проблему розв’язуваності” - знаходження загального методу для визначення виконуваності даного вислову на мові формальної логіки.
Стаття Тюрінга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв’язуваною. Але значення статті Тюрінга виходило далеко за межі тієї задачі, з приводу якої вона була написана.
Варто навести характеристику цієї роботи, що належить Джону Хопкрофту: “Працюючи над проблемою Гільберта, Тюрінгу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про певний алгоритм, тобто процедурі, яка може бути виконана механічно, без творчого втручання, він показав, як цю ідею можна втілити у вигляді точної моделі обчислювального процесу. Отримана модель обчислень, у якій кожний алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названою згодом машиною Тюрінга”.
Машина Тюрінга є розширенням моделі кінцевого автомата, розширенням, що включає потенційно нескінченну пам’ять з можливістю переходу (рух) від оглядаючої в даний момент комірки до її лівого або правого сусіда.
Алан Тьюрінг висловив припущення, що будь-який алгоритм в інтуїтивному значенні цього слова може бути представлений еквівалентною машиною Тюрінга. Це припущення відоме як теза Чорча–Тюрінга. Кожний комп’ютер може моделювати машину Тюрінга (операції перезапису комірок, порівняння і переходу до іншої сусідньої комірки з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і з цієї тези виходить, що всі комп’ютери (незалежно від потужності, архітектури тощо) еквівалентні з погляду принципової можливості рішення алгоритмічних задач.
2.4.2 Структурна схема Машини Тьюрінга
Структуру моделі машини Тюрінга, склад її блоків та їх взаємодію можна задати у вигляді наступної структурної схеми:
Рис.2 Структура моделі машини Тюрінга
На цій схемі відображено розділення пам’яті на зовнішню і внутрішню. Зовнішня пам’ять зображена комірками нескінченної стрічки, які призначені для зберігання інформації, закодованої в символах зовнішнього алфавіту, внутрішня пам’ять - двома комірками для зберігання чергової команди: q-комірка зберігає знак стану і p- комірка - знак зсуву. У цих двох комірках відбувається затримка знаків qs і r, отриманих на виході логічного блоку L в даному такті роботи, до початку наступного такту. З q- комірка по лінії зворотного зв'язку у логічний блок L поступає знак стану qj, вироблений цим же блоком на попередньому такті. З p- комірка знак зсуву прямує у механізм зсуву, керуючи переміщенням каретки.
Логічний блок "спілкується" із зовнішньою пам'яттю за допомогою читаючої і записуючої головки (каретки); головка на схемі зображена прямокутником, встановленим проти "оглядаючого комірки".
Ми можемо описати машину Тьюрінга використовуючи 4-х позиційний кортеж. На рис.3 представлено кортежі програми простої машини Тьюрінга.
<s0, 1, s0, » >
< s0, 0, s1, 1 >
< s1, 1, s1, « >
< s1, 0, s2, » >
Рис.3 Приклад програми машини Тьюрінга
Наведемо інтерпретацію символів, як ізаписуються на магнітну стрічку. Наприклад, якщо ми збираємося спроектувати машину, яка виконуватиме деяку математичну функцію, скажемо, додавання, тоді нам потрібно описати інтерпретацію одиниць і нулів, які з’являтимуться на стрічці.
У прикладі ми представлятимемо число n як блок із n+1 копій символа ‘1’ на стрічці. Таким чином ми представлятимемо цифру 0 як одна ‘1’, а цифру 3 як блок із чотирьох ‘1’.
Ми також повинні зробити деякі припущення на рахунок конфігураціїї стрічки на момент початку виконання програми, і на момент закінчення - для того, щоб мати основу для інтерпретації обчислень. Ми припускаємо, що якщо функція, яка має бути обчислена вимагає n аргументів, тоді машина Тьюрінга починатиме виконання алгоритму і найлівішого положення головки запису/зчитування. Блоки одиниць, які представляють аргументи мають бути відокремлені одним символом ‘0’. Наприклад, для обчислення суми 3+4, машина Тьюрінга почне виконання алгоритму у наступній конфігурації (рис.5), де три крапки позначає нулі, які ми не можемао побачитина безмежній стрічні, а стрілка вказує комурку, яка зчитується у даний момент.
Рис.5 Початкова конфігурація для операції додавання
Машина повинна закінчити виконання алгоритму такоє у стандартній конфігурації. На стрічці повинен бути єдиний блок ‘1’, і машина повинна зчитувати найлівішу ‘1’. Якщо машина коректно обчислила функцію, тоді цей блок повинен представляти правильний результат. Отож, машина, яка виконує операцію додавання, розпочавши із початкової конфігурації (рис.5) повинна завершити роботу у конфігурації, що зображена на рис.6:
Рис.6 Кінцева конфігурація для операції додавання
Приймаючи такі правила для кінцевої конфігурації машини Тьюрінга випливає, що ми можемо компонувати машини ідентифікуючи кінцевий стан однієї машини із початковим станом наступної.
Згідно до цих умов, діаграма станів на рис.4 описує машину, яка обчислює функцію знаходження наступного числа. Починаючи із стандартної конфігурації, коли на стрічці представлене число n, машина припинить роботу у стандартній конфігурації, яка представляє число n+1. Це робиться шляхом використання стану s0 длч сканування першого ‘0’ справа від єдиного блоку ‘1’. Тоді він заміняє ‘0’ на ‘1’, і скнує назад уліво перебуваючи вже у стані s1 доти, доки не натрапимо на ‘0’ (це є перший нуль наліво від блоку ‘1’) Тоді здійснюється один перехід назад до першої одиниці блоку і зупиняється у стані s2.
Ця машина нагадує машину знаходження наступного елементу (рис.4) у присутності переходу іх стану s0 у стан s 2 , томущо машина має вписати ‘1’ направо від першого блоку одиниць, а потім повернутися до першої найлівішої ‘1’. Починаючи із стандартної конфігурації для додавання, машина повинна об’єднати два блоки ‘1’ у один блок, який містить (n+1)+1+(m+1) копій символа ‘1’, тому, перейшовши у стан s2 стрічка представляє число n+m+2. Для виправлення результату необхідно перемістити дві копії ‘1’, які отримуються у станах s 2 і s3, кожний з яких замінює ‘1’ нулями і тоді пересуває магнітну головку у крайнє ліве положення.
Оскільки стрічка початково містить принаймні дві ‘1’ і ми маємо дописати ще одну, тому стирання двох ‘1’ залишить принаймні одну на стрічці у кінці обчислень, і ми проскануємо всі до крайної лівої позиції.
2.4.3 Конфігурації роботи машини Тьюрінга
Повний стан машини Тьюрінга у будь-який момент часу під час обчислень може бути описаний назвою стану, у якому перебуває машина, символами на стрічці і коміркою, яка у даний момент зчитується. Опис цих трьох даних називається миттєвим описом конфігурації обчислень. Графічне представлення такого опису представлено на рис.8, у якому стрілка показує на скановану у даний момент часу комірку, а назва стану вказана поруч із стрілкою.
Рис.8 Миттєва конфігурація обчислень машини Тьюрінга
2.4.4 Формулювання визначення машин Тьюрінга
Наразі було представлено найзагальніше представлення ідеї ашин Тьюрінга. Існує кілька варіантів формулювання машини Тьюрінга, які є еквівалентними до розглянутого, і різні автори використовуючи будь-який з них. Оскільки всі визначення машини Тьюрінга еквівалентні одне одному, то ми можемо вибрати серед цих формулювань будь-яке, що нам найбільше підходить.
Формулювання F1 і формулювання F2 є еквівалентними якщо для будь-якої описаної у формулюванні F1 існує машина, описана у F2 яка має ту саму поведінку введення-виведення, і навпаки, наприклад, коли розпочинає обчислення з тієї самої комірки на стрічці і завершує роботи на тій самій стрічці у тій самій комірці.
2.4.5 Безмежні двосторонні стрічки
У початково наведеному формулюванні ми визначили, що стрічка має кінець, скажімо зліва, nі простягається безмежно далеко вправо. Якщо припустити, що стрічка буде безмежною, як у правому напрямку, так і у лівому, то це призведе до нового формулювання машини Тьюрінга, еквівалентне першому. Для будь-якої машини Тьюрінга, яка використовує двосторонню безмежну стрічку існує машина Тьюрінга і односторонньою безмежною стрічкою із однаковою повекдінкою при введенні/виведенні, і навпаки.
2.4.6 Двохвимірні стрічки
Замість одновимірної безмежної стрічки можна розглідати двохвимірну “стрічку”, яка простягається безмежно вгору і вниз, так само як у ліво і вправо. Ми додамо до визначення, що машинна може переміщати головку читання-запису вгору і вниз на одну комірку, у додачу до існуючих рухів у право і вліво. Дане формулювання знову є еквівалентним початковому.
2.4.7 Довільний рух головки
Модифікуючи визначення машини Тьюрінга у моменті руху головки читання-запису на довільну кількість комірок у визначеному напрямку не змінює поняття машини Тьюрінга.
2.4.8 Довільна кількість головок читання-запису
Машина Тьюрінга може мати довільну кількість головок читання-запису. Це також не змінює поняття машини Тьюрінга.
2.4.9 Довільний скінчений алфавіт
У початковому формулюванні ми дозволили використання лише двох символів на стрічці. Проте, можна розширити кількість символів до будь-якого обмеженого алфавіту.
Загальний випадок опису машини Тьюрінга є дозволити машині і записувати і рухати головку у тому самому напрямку. Це вимагає заміни початкового 4-х позиційного кортежу на 5-позиційний:
<Стан0, Символ, Станновий, Символновий, Переміщення>
де Символновий є записаним символом, і Переміщення є одним із зсувів вліво і вправо.
Ця додаткова свобода не впливає на нове визначення машини Тьюрінга. Тому що для кожної нової машини Тьюрінга існують старі машини із тими самими властивостями.
2.4.10 Недетерміновані машини Тьюрінга
Очевидно радикальніше переформулювання визначення мишини Тьюрінга дозволяє ввести поняття паралельних альтернативних обчислень. У початковому формулюванні було сказано, що машина визначається для багаторазових переходів для заданої пари стан/символ, і машина може перебувати у такому стані, в якому обчислення припиняються. У даному переформулюванні, розглядаються всі переходи, і всі результуючі обчислення відбуваються паралельно. Один із шляхів візуалізації такого порядку є генерування машиною точної копії самої себе і стрічки для кожного можливого альтернативного переміщення, і кожні машина продовжує обчислення. Якщо будь-яка із машин успішно завершить обчислення, тоді загальне обчислення припиняється і наслідує результуючу стрічку. У даному формулюванні, деякі стани визначаються як прийнятні стани і коли машина зупиняється в одному із таких станів, тоді обчислення є успішним, інакше обчислення є неуспішним і будь-яка інша мшина продовжує свою роботу до настання результуючого стану.
Введення поняття недетермінованої мишини Тьюрінга не змінює загальног визначення мишини Тьюрінга. Початкове формулювання Тьюрінгом використовувало 5-ти позиціний кортеж для мишини Тьюрінга. Пост запропонував 4-х позиційне представлення і використання безмежної у дві сторони стрічки.
2.4.11 Ускладення машини Тьюрінга
У додаток до виконання арифметичних функцій використовуючи унарне представлення чисел, ми можемо виконувати такі завдання, як копіювання блоків символів, стирання блоків символів тощо. На рис.9 показано приклад мишини Тьюрінга яка після стартування із стандартної конфігурації на стрічці, що містить єдиний блок ‘1’, зупиняється на стрічці, яка містить уже дві копії цього блоку ‘1’. Блоки розділені ‘0’. Мишина Тьюрінга містить алфавіт, який складається із символів ‘0’, ‘1’ і ‘A’.
Дія цієї машини полягає у повторюваній заміні “1” одного початкового блоку на A, і тоді запис нових ‘1’ справа від решти ‘1’ на стрічці, після залишення нуля між початковим блоком і копією. Тоді машина повертається до блоку із A і перетворює ці символи назад в ‘1’.
Початковий стан s0 використовується для заміни ‘1’ на ‘A’, і переміщення стрічки вправо з переходом у стан s1. У стані s1 ми проходимо решту блоку ‘1’ поки не дійдемо до ‘0’ (розділювача блоків) і у стані s2 ми проходимо всі ‘1’ до найправішого ‘0’ (це є копіювання блоку ‘1’, який ми створюємо). Коли ми досягаємо кінця блоку ми натрапляємо на ‘0’, який ми перетворюємо на ‘1’ і повертаємо уліво і переходимо у стан s3. Стани s3 і s4 переміщають стрічку уліво минаючи всі ‘1’ і розділювач ‘0’ на стрічці доки не дійдемо до ‘A’. Коли ми натрапимо на ‘A’ ми переходимо у стан s0 і рухаємося у право.
У цій точці програми ми або зчитуємо наступну ‘1’ першого блоку, або перший блок весь складається із символів ‘A’, і ми зчмтуємо розподілювач ‘0’. У попередньому випадку ми повторюємо наші дії від стану s1 до стану s4, але в останньому ми переходимо у стан s5, рухаючись вліво. У цьому випадку ми ітераційно знаходимо символи ‘A’, які замінюємо на ‘1’, і рухаємося вліво. Якщо ми натрапимо на ‘0’, тоді всі символи ‘A’ були перетворені назад в ‘1’. Ми будемо щукати ‘0’ від початкової комірки, і таким чином рухатися вправо, і переходити у кінцевий стан s6.
Ця машина копіювання може бути об’єднана із машиною додавання, представленою на рис.4 для створення нової машини, яка здійснюватиме подвоєння числа n: 2n. Це може бути реалізовано спершу виконавши копіювальну машину для отримання стрічки із двома копіями числа n, і тоді застосовуючи машину додавання для обчислення n+n (=2n). Ми можемо зробити це ідентифікуючи кінцевий стан копіювальної машини (s6) із початковим станом (s0) машини додавання.
Машини Тьюрінга є дуже потужними. Для будь-якого кількості обчислювальних задач можна побудувати машину Тьюрінга. Було показано, що можливо спроектувати машину Тьюрінга для арифметичних дій над натуральними числами.
Перша робота Тьюрінга зосереджувала увагу на обчислювальних числах. Число є обчислювальне за Тьюрінгом якщо існує машина Тьюрінга, яка починаючи роботц із порожньої стрічки обчислює приблизно точнк наближення до даного числа. Всі алгебраїчні цисла (корені поліномів із алгебраїчними коефіцієнтами) і багато інших математичних констант, таких як e і π є обчислювальні за Тьюрінгом.
Машина Тьюрінга може набагато більше ніж записувати цифри у комірки. Серед інших дій вона може обчислювати числовві функції, наприклад машина для додавання (зображена на рис.4), множення, ділення, взяття експоненти, обчислення факторіалу тощо.
Приймаючи правила представлення TRUE і FALSE, TRUE представимо групою із двох ‘1’, а FALSE однією ‘1’; ми можемо обчислити характеристичні функції обчислювальних предикатів, і ми можемо комбінувати результати таких функцій використовуючі булеві функції: AND, NOT, OR, IF-THEN-ELSE. Як відомо Характеристичною функцiєю довільної множини А(U називається функцiя (А: U({0,1} така: (А(а) =
Обчислювальні за Тьюрінгом функції є рекурсивними функціями.
2.4.12 Універсальна машина Тьюрінга
Різні алгоритми виконуються на різних машинах Тьюрінга, які відрізніються своїми функціональними схемами. Проте можна побудувати Універсальну Машину Тьюрінга (УМТ), яка здатна виконувати будь-який алгоритм, а значить здатну виконувати роботу будь-якої машини Тьюрінга. Коли УМТ подати стрічку, що містить закодовану іншу машину Тьюрінга, назвемо її T, а за нею вхідні дані для T, УМТ отримає той самий результат, що і T. УМТ може наслідувати поведінку будь-якої машини Тьюрінга (включаючи себе).
УМТ можна вважати програмованим комп’ютером. Коли УМТ надати програму (опис іншої машини), вона функціонуватиме, ніби це задана машина обробляє вхідну стрічку. Слід зауважити ідентифікацію еквівалентності введення-виведення до “функціонує еквівалентно ”. Машина T працюючи над введеною інформацією t імовірно виконуватьиме менше переміщень ніж УМТ,яка симулює машину T яка обробляє t.
Для того, щоб спроектувати таку машину спершу необхідно визначити представлення машини Тьюрінга на стрічці для оброблення УМТ. Щоб зробити це, необзідно нагадати, що машина Тьюрінга формально представляється набором 4-х позиційних кортежів. Спершу закодуємо однин кортеж, а потім весь набір.
Кожний 4-х позиційний кортеж у специфікації машини буде закодований як набір чотирьох блоків ‘1’, розділених одним ‘0’
Перший блок одиниць кодуватиме біжучий стан, використовуючи прийняте нами положення про унарні числа (n+1 одиниць представляє число n).
Другий блок одиниць кодує біжучий символ, використовуючи ‘1’ для представлення цифри нуль, і дві для представлення цифри ‘1’ (не можна використати нуль для представлення ‘0’.)
Третій елемент кортежа представлятиме новий стан в унарній нотації.
Четвертий елемент представлятиме дію, і існує 4 можливості: символи будуть кодовані аналогічно, як це зроблено вище. Блок із трьох ‘1’ представлятиме рух вліво («), а блок із чотирьох ‘1’ представлятиме рух вправо (»).
17.07.2020 14:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора