ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2341
Скачиваний: 1
26
Одна команда для машини Тьюринга якраз і являє собою конкретну
комбінацію цих трьох складових: вказівок, який символ записати в комірку
(над якою стоїть автомат), куди пересунутися і в який стан перейти. Хоча
команда може містити і не всі складові (наприклад, не змінювати символ, не
пересуватися або не змінювати внутрішній стан).
27
Приклад 1.
Припустимо, на стрічці є слово, яке складається з символів #, $, 1 і 0
Потрібно замінити всі символи # і $ на нулі. В момент запуску каретка
знаходиться над першою літерою слова зліва. Завершується програма тоді,
коли каретка знаходиться над порожнім символом після літери слова, що є
останньою з права.
Примітка: довжина
слова
і
послідовність
символів
значення не мають.
На
рисунку
наводиться
приклад
послідовності
виконання
команд
для
конкретного
випадку.
Якщо
на
стрічці
буде інше
слово
,
то
і
послідовність
виконання
команд
буде іншою.
Незважаючи
на
це
,
дана
програма
для
машини
Тьюринга
(
на
рисунку
–
таблиця
зліва
)
застосовна
до будь-яких
слів
описаного
зовнішнього
алфавіту
(дотримується
властивість
застосовності
алгоритму
до всіх
однотипних
завдань
–
масовість).
Приклад 2.
Зовнішній алфавіт має вигляд А={0,1,2,3,4,5,6,7,8,9}.
Нехай Р – не порожне слово, тобто Р – це послідовність з десяткових
невід’ємних цифр.
Треба отримати на стрічці запис числа, яке на одиницю більше ніж число
Р.
Рішення.
Для рішення цієї задачі необхідно виконати наступні дії:
1. Перегнати автомат під останню цифру числа.
2. Якщо це цифра від 0 до 8, то замінити її цифрою на 1 більше і
зупинитися, наприклад:
1
9
5
7
→
1
9
5
7
→
1
9
5
8
↑ ↑ ↑
3. Якщо це цифра 9, тоді замінити її на 0 і перемістити автомат до
попередньої цифри.
Після чого збільшити на одиницю передостанню цифру.
Наприклад:
28
6
4
9
→
6 4 9
→
6
4 0
→
6 5 0
↑ ↑ ↑ ↑
4.
Особливий випадок.
В Р є тільки дев’ятки (наприклад, 99).
Тоді автомат буде переміщуватися вліво, змінюючи дев’ятки на нулі, і в
конці кінців опиніться під порожньою клітинкою.
В цю пустую клітинку треба записати 1 і зупинитися (відповіддю буде
100):
9
9
→
9
9
→
9
0
→
0
0
→
1
0
0
↑ ↑ ↑ ↑ ↑
У програми для машини Тюринга ці дії описуються наступним чином:
0
1
2
3
4
5
6
7
8
9
Λ
q1
0,R,q1
1,R,q1
2,R,q1
3,R,q1
4,R,q1
5,R,q1
6,R,q1
7,R,q1
8,R,q1
9,R,q1
Λ
,R,q2
q2 1,N,!
2,N,!
3,N,!
4,N,!
5,N,!
6,N,!
7,N,!
8,N,!
9,N,!
0,L,q2 1,N,!
Пояснення.
q1 –
це стан, в якому автомат «біжить» під останню цифру числа. Для
цього він весь час рухається вправо, не змінюючи видимі цифри і
залишаючись у тому ж стані.
Але тут є одна особливість: коли автомат перебуває під останньою
цифрою, то він ще не знає про це (адже він не бачить, що записано в сусідніх
клітинах) і визначить це лише тоді, коли потрапить на порожню клітину.
Тому, дійшовши до першої порожній клітини, автомат повертається
назад під останню цифру і переходить в стан q2 (вправо рухатися вже не
треба).
q2 –
це стан, в якому автомат додає 1 до тієї цифри, яку бачить в даний
момент.
29
Спочатку це остання цифра числа:
-
якщо вона – в діапазоні від 0 до 8, то автомат замінює її цифрою,
яка на 1 більше, і зупиняється.
-
Але якщо це цифра 9, то автомат замінює її на 0 і зсувається
вліво, залишаючись в стані q2.
Тобто, тепер він буде додавати 1 до попередньої цифри. Якщо і ця цифра
дорівнює 9, то автомат замінює її на 0 і зсувається вліво, залишаючись в стані
q2,
оскільки повинен виконати те ж саме діяння – збільшить на 1 видиму
цифру. Якщо ж автомат зрушився вліво, а у видимій клітці немає цифри (а є
«
пусто»), то він записує сюди 1 і зупиняється.
Відзначимо, що для порожнього вхідного слова наша задача не
визначена, тому на цьому слові машина Тюринга (МТ) може вести себе як
завгодно. У нашій програмі, наприклад, при порожньому вхідному слові МТ
зупиняється і видає відповідь 1.
Вище наведений запис програми в повному, нескороченому вигляді.
Наведемо запис програми в скороченому, більш наочному вигляді, при
цьому праворуч дамо коротке пояснення дій, які реалізуються у відповідних
станах автомата:
0
1
2
3
4
5
6
7
8
9
ʌ
q1
,R,
,R,
,R,
,R,
,R,
,R,
,R,
,R,
,R,
,R,
,L, q2
Під
останню
цифру
q2
1,,!
2,,!
3,,!
4,,!
5,,!
6,,!
7,,!
8,,!
9,,!
0,L,
1,,!
Цифра +1,
яка є
видимою
3.2 Властивості машини Тьюринга як алгоритму
На прикладі машини Тьюринга добре простежуються властивості
алгоритмів.
30
-
Дискретність. Машина Тьюринга може перейти до (к + 1)-го кроку
тільки після виконання к-го кроку, оскільки саме к-й крок визначає, яким буде
(до + 1) -й крок.
-
Зрозумілість. На кожному кроці в комірку пишеться символ з алфавіту,
автомат робить один рух (Л, П, Н) і машина Тьюринга переходить в один з
описаних станів.
-
Детермінованість. У кожній клітці таблиці машини Тьюринга
записаний лише один варіант дії. На кожному кроці результат визначений
однозначно, отже, послідовність кроків розв'язання задачі визначена
однозначно, тобто якщо машині Тьюринга на вхід подають одне й те ж слово,
то вихідне слово кожен раз буде одним і тим же.
-
Результативність. Змістовно результати кожного кроку і всієї
послідовності кроків визначені однозначно, отже, правильно написана
машина Тьюринга за кінцеве число кроків перейде в стан q0, тобто за кінцеве
число кроків буде отримана відповідь на питання задачі.
-
Масовість. Кожна машина Тьюринга визначена над усіма допустимими
словами з алфавіту, в цьому і полягає властивість масовості. Кожна машина
Тьюринга призначена для вирішення одного класу задач, тобто для кожного.
3.3 Проблеми, які не розв'язуються алгоритмічно
За час свого існування людство придумало безліч алгоритмів для
вирішення різноманітних практичних і наукових проблем. Виникає
питанням – а чи існують які-небудь проблеми, для яких неможливо
придумати алгоритми їх вирішення?
Успіхи математики до кінця XIX століття привели до формування думки,
яку висловив Д. Гілберт – «в математиці не може бути проблем, які не
розв'язуються алгоритмічно», на конгресі 1900 року в Парижі.
Першою фундаментальною теоретичною роботою, пов'язаною з доказом
алгоритмічної нерозв'язності, була робота Курта Геделя – його відома теорема
про неповноту символічних логік.
Зусиллями різних дослідників список алгоритмічно нерозв'язних
проблем був значно розширений. Сьогодні прийнято при доказі
алгоритмічної нерозв'язності деякої задачі зводити її до класичної задачі –
«задачі зупину».