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

Щоб задати конкретну машину Т'юрінга, потрібно описати для неї такі складові:

Зовнішній алфавіт.Кінцева множина (позначають буквою А), елементи якої називаються буквами (символами). Одна з літер цього алфавіту (наприклад, а0) повинна бути порожнім символом.

Наприклад, алфавіт машини Тьюринга, що працює з двійковими числами, визначається у вигляді A = (0, 1, а0).

Безперервний ланцюжок символів на стрічці називають словом.

Автоматомназивають пристрій, що працює без участі людини. Автомат у машині Тьюринга має кілька станів і за певних умов переходить із одного стану до іншого. Безліч станів автомата називають внутрішнім абеткою.

Внутрішній алфавіт. Кінцева множина станів каретки (автомата). Позначається літерою Q = (q1, q2 ...). Один із станів - q1- повинен бути початковим (що запускає програму). Ще один із станів (q0) має бути кінцевим (завершальним програму) – стан зупинка.

Таблиця переходів.Опис поведінки автомата (каретки) залежно від стану та ліченого символу.

Автомат машини Тюрінга в процесі своєї роботи керується програмою, під час кожного кроку якої виконуються наступні дії:

Записувати символ зовнішнього алфавіту в комірку (у тому числі й порожній), замінюючи в ній (у тому числі й порожній).

Пересуватися на одну комірку вліво або вправо.

Міняти свій внутрішній стан.

Тому при складанні програмидля кожної пари (символ, стан) необхідно визначити три параметри: символ ai з вибраного алфавіту A, напрямок переміщення каретки ("←" - вліво, "→" - вправо, "точка" - немає переміщення) та новий стан автомата qk.

Наприклад, команда 1 "←" q2означає "замінити символ на 1, перемістити каретку вліво на одну комірку і перейти в стан q2".

Передбачається, що універсальний виконавець має вміти доводити існування чи відсутність алгоритму тієї чи іншої завдання.

Запитання 28

Теза Тьюринга - прийняте без доказу фундаментальне становище теорії алгоритмів, за яким всякий алгоритм представимо у вигляді машини Тьюринга.

Програма машини Тюрінга (Р) -сукупність всіх команд, Програма подається у вигляді таблиці та називається Т'юрінговою функціональною схемою.

	a 0	a 1	a 2
q 1	а 0 Пq 1	a 1 Пq 1	a 2 Лq 2
q 2	а 1 Пq 2	a 2 Нq 0	a 0 Нq 0

Запитання 29

Машини Т'юрінга з двома виходами

Припустимо, ми розширили визначення машини Тьюринга, додавши у пристрій керування машини певний стан q*. Будемо говорити, що й пристрій управління перетворюється на стан q0 для заданого вхідного слова х, то машина допускає х. Якщо пристрій керування входить у стан q*, то машина забороняє х. Такий пристрій називатимемо машиною Тьюринга з двома виходами.

Виявляється, що якщо задані дві машини Тьюринга T1 і Т2, які допускають безліч слів Х1 і Х2, що не перетинаються, відповідно, то завжди можна побудувати машину Тьюринга T3 з двома виходами, яка буде допускати Х1 і забороняти Х2. Ці машини Т'юрінга будуть нам корисні при розгляді питання про дозвіл.

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

Питання 30

Багатострічкова машина Тьюринга складається з кінцевого керування з k стрічковими головками, по одній на кожній стрічці (рис. 6.4).

Кожна стрічка нескінченна в обох напрямках. При одному русі, що залежить від стану кінцевого керування та сканованого символу кожної зі стрічкових головок, машина може: 1) змінити стан; 2) надрукувати новий символ на кожному із сканованих осередків; 3) пересунути кожну з її стрічкових головок незалежно один від одного на одну комірку вліво, вправо або залишити її на тому самому місці.

Спочатку вхідний ланцюжок є лише на першій стрічці, а всі інші стрічки порожні. Ми не визначатимемо цей пристрій більш формально, надаючи це читачеві.

Теорема 6.2. Якщо мова L приймається багатострічковою машиною Тьюринга, він приймається одноленточной машиною Тьюринга. Доведення. Нехай мова L приймається машиною Тьюринга T1 з стрічками. Побудуємо однострічкову машину Тьюринга T2 з 2k доріжками, по дві для кожної зі стрічок машини T1. На одній доріжці записується вміст відповідної стрічки машини T1, а інша - порожня, за винятком маркера в комірці, що містить символ і відповідною головкою, що сканується машини T1. Такий пристрій для моделювання трьох стрічок у вигляді однієї ілюструється рис. 6.5. Кінцеве керування машини T2 запам'ятовує, які маркери головок машини T1 знаходяться ліворуч, а які справа від головки T2. Стан машини T1 теж запам'ятовуються в кінцевому керуванні машини T2.

Щоб моделювати рух машини T1, машина T2 повинна відвідати кожне вічко з маркером головки, реєструючи по черзі символ, сканований відповідною головкою T1. Коли машина T2 проходить через маркер головки, вона повинна уточнювати напрямок, у якому слід шукати маркер. Після збирання всієї необхідної інформації машина T2 визначає рух машини T1. Потім машина T2 відвідує по черзі кожен з маркерів головок знову, змінюючи марковані комірки і зсуваючи маркери на одну комірку, якщо потрібно. Звичайно, якщо новий стан приймає, то машина T2 приймає вхідний ланцюжок.

І, згідно з тезою Чорча - Тьюринга, здатна імітувати всіх виконавців(за допомогою завдання правил переходу), які реалізують процес покрокового обчислення, в якому кожен крок обчислення досить елементарний.

Тобто будь-який інтуїтивний алгоритм може бути реалізований за допомогою деякої машини Тьюринга.

Пристрій

До складу машини Т'юрінга входить необмежена в обидві сторони стрічка(можливі машини Тьюринга, які мають кілька нескінченних стрічок), поділена на комірки, і керуючий пристрій(також називається головкою запису-читання (ГЗЛ)), здатне перебувати в одному з безлічі станів. Число можливих станів пристрою, що управляє, звичайно і точно задано.

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

Керуючий пристрій працює згідно правилам переходуякі представляють алгоритм, реалізованийданою машиною Тьюринга. Кожне правило переходу наказує машині, залежно від поточного стану та спостерігається в поточній клітині символу, записати в цю клітину новий символ, перейти в новий стан і переміститися на одну клітинку вліво або вправо. Деякі стани машини Т'юрінга можуть бути позначені як термінальні, і перехід у будь-яке з них означає кінець роботи, зупинку алгоритму.

Машина Тьюринга називається детермінованою, якщо кожній комбінації стану та стрічкового символу в таблиці відповідає не більше одного правила. Якщо існує пара «стрічковий символ - стан», для якої існує 2 і більше команд, така машина Т'юрінга називається недетермінованою.

Опис машини Тьюринга

Конкретна машина Тьюринга задається перерахуванням елементів множини літер алфавіту A, множини станів Q і набором правил, якими працює машина. Вони мають вигляд: q i a j →q i1 a j1 d k (якщо головка знаходиться в стані q i , а в осередку записана буква a j , то головка переходить в стан q i1 , в комірку замість a j записується a j1 , головка робить рух d k , яке має три варіанти: на комірку вліво (L), на комірку вправо (R), залишитися на місці (N)). Для кожної можливої ​​конфігурації є одно правило (для недетермінованої машини Тьюринга може бути більше правил). Правил немає тільки для заключного стану, потрапивши до якого машина зупиняється. Крім того, необхідно вказати кінцевий та початковий стани, початкову конфігурацію на стрічці та розташування головки машини.

приклад

Приклад машини Тьюринга для множення чисел в унарній системі числення. Запис правила «q i a j →q i1 a j1 R/L/N» слід розуміти так: q i - стан при якому виконується це правило, a j - дані в комірці, в якій знаходиться головка, q i1 - стан, в який потрібно перейти, a j1 - що потрібно записати в комірку, R/L/N – команда на переміщення.

Машина працює за наступним набором правил:

	q 0	q 1	q 2	q 3	q 4	q 5	q 6	q 7	q 8
1	q 0 1→q 0 1R	q 1 1→q 2 aR	q 2 1→q 2 1L	q 3 1 → q 4 aR	q 4 1→q 4 1R			q 7 1→q 2 aR
×	q 0 ×→q 1 ×R		q 2 ×→q 3 ×L		q 4 ×→q 4 ×R		q 6 ×→q 7 ×R		q 8 ×→q 9 ×N
=			q 2 =→q 2 =L		q 4 =→q 4 =R			q 7 =→q 8 =L
a			q 2 a→q 2 aL	q 3 a→q 3 aL	q 4 a→q 4 aR		q 6 a→q 6 1R	q 7 a→q 7 aR	q 8 a→q 8 1L
*	q 0 *→q 0 *R			q 3 *→q 6 *R	q 4 *→q 5 1R
						q 5 →q 2 *L

Опис станів:

початок
q 0	початковий стан. Шукаємо "x" праворуч. При знаходженні переходимо у стан q1
q 1	замінюємо "1" на "а" і переходимо в стан q2
Переносимо всі «1» з першого числа на результат
q 2	шукаємо "х" зліва. При знаходженні переходимо у стан q3
q 3	шукаємо "1" зліва, замінюємо її на "а" і переходимо в стан q4. Якщо «1» закінчилися, знаходимо «*» і переходимо в стан q6
q 4	переходимо в кінець (шукаємо "*" праворуч), замінюємо "*" на "1" і переходимо в стан q5
q 5	додаємо «*» в кінець і переходимо в стан q2
Обробляємо кожен розряд другого числа
q 6	шукаємо "х" праворуч і переходимо в стан q7. Поки що шукаємо замінюємо «а» на «1»
q 7	шукаємо «1» або «=» праворуч при знаходженні «1» замінюємо його на «а» і переходимо у стан q2 при знаходженні "=" переходимо в стан q8
Кінець
q 8	шукаємо "х" зліва. При знаходженні переходимо у стан q9. Поки що шукаємо замінюємо «а» на «1»
q 9	термінальний стан (зупинення алгоритму)

Помножимо за допомогою МТ 3 на 2 одиничній системі. У протоколі вказано початковий та кінцевий стан МТ, початкова конфігурація на стрічці та розташування головки машини (підкреслений символ).

Початок. У стані q 0 , ввели у машину дані: *111x11=*, головка машини розташовується першому символі *.

1-й крок. Дивимося по таблиці правил, що робитиме машина, перебуваючи в стані q 0 і над символом «*». Це правило з 1-го стовпця 5-го рядка - q0*→q0*R. Це означає, що ми переходимо в стан q 0 (тобто не змінюємо його), символ стане «*» (тобто не зміниться) і зміщуємося за введеним текстом «*111x11=*» вправо на одну позицію (R), то є на 1-й символ 1. У свою чергу стан q 0 1 (1-й стовпець 1-й рядок) обробляється правилом q 0 1→q 0 1R. Тобто знову відбувається просто перехід праворуч на 1 позицію. Так відбувається, доки ми не станемо на символ «х». І так далі: беремо стан (індекс при q), беремо символ, на якому стоїмо (підкреслений символ), з'єднуємо їх та дивимося обробку отриманої комбінації за таблицею правил.

Простими словами, алгоритм множення наступний: помічаємо 1 одиницю 2-го множника, замінюючи її на букву «а», і переносимо весь 1-й множник за знак рівності. Перенесення здійснюється шляхом почергової заміни одиниць одного множника на «а» та дописування такої ж кількості одиниць наприкінці рядка (ліворуч від крайнього правого «*»). Потім міняємо все "а" до знака множення "х" назад на одиниці. І цикл повторюється. Справді, адже A помножити на можна уявити як А+А+А В раз. Помічаємо тепер 2 одиницю 2-го множника буквою «а» і знову переносимо одиниці. Коли до знака "=" не виявиться одиниць - значить множення завершено.

Повнота по Тьюрингу

Можна сказати, що машина Тьюринга є найпростішою обчислювальною машиною з лінійною пам'яттю, яка згідно з формальними правилами перетворює вхідні дані за допомогою послідовності елементарних дій.

Елементарність дій полягає в тому, що дія змінює лише невеликий фрагмент даних у пам'яті (у випадку машини Тьюринга - лише один осередок), і кількість можливих дій не нескінченна. Незважаючи на простоту машини Т'юрінга, на ній можна обчислити все, що можна обчислити на будь-якій іншій машині, яка здійснює обчислення за допомогою послідовності елементарних дій. Ця властивість називається повнотою.

Один із природних способів доказу того, що алгоритми обчислення, які можна реалізувати на одній машині, можна реалізувати і на іншій – це імітація першої машини на другій.

Імітація полягає у наступному. На вхід до другої машини подається опис програми (правил роботи) першої машини D (\displaystyle D)та вхідні дані X (\displaystyle X), які мали надійти на вхід першої машини. Потрібно описати таку програму (правила роботи другої машини), щоб у результаті обчислень на виході виявилося те саме, що повернула б перша машина, якби отримала на вхід дані X (\displaystyle X).

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

На машині Тьюринга можна імітувати машину Поста, нормальні алгоритми Маркова та будь-яку програму для звичайних комп'ютерів, що перетворює вхідні дані у вихідні за якимось алгоритмом. На різних абстрактних виконавцях можна імітувати Машину Тьюринга. Виконавці, для яких це можливо, називаються повними по Тьюрингу(Turing complete).

Існують програми для звичайних комп'ютерів, що імітують роботу машини Тьюринга. Але слід зазначити, що дана імітація неповна, тому що в машині Тьюринга є абстрактна нескінченна стрічка. Нескінченну стрічку з даними неможливо повною мірою імітувати на комп'ютері з кінцевою пам'яттю: сумарна пам'ять комп'ютера - оперативна пам'ять, жорсткі диски, різні зовнішні носії даних, регістри та кеш процесора та ін. - може бути дуже великою, але завжди завжди кінцева. Теоретична межа кількості інформації, яка може знаходитися всередині заданої поверхні, з точністю до множника 1 / ln ⁡ 2 (\displaystyle 1/\ln (2))дорівнює ентропії чорної дірки з тією самою площею поверхні.

Варіанти машини Тюрінга

Модель машини Т'юрінга допускає розширення. Можна розглядати машини Тьюринга з довільним числом стрічок та багатовимірними стрічками з різними обмеженнями. Однак усі ці машини є повними за Тьюрингом і моделюються звичайною машиною Тьюринга.

Машина Тьюринга, що працює на напівнескінченній стрічці

Як приклад такого відомості розглянемо таку теорему: Для будь-якої машини Тьюринга існує еквівалентна машина Тьюринга, що працює на напівнескінченній стрічці (тобто на стрічці, нескінченній в один бік).

тренажер для вивчення універсального виконавця

Що це таке?

Тренажер «Машина Тьюринга» — це навчальна модель універсального виконавця (абстрактної обчислювальної машини), запропонованого в 1936 А. Тьюрингом для уточнення поняття алгоритму. Відповідно до тези Тьюринга, будь-який алгоритм може бути записаний як програми для машини Тьюринга. Доведено, що машина Тьюринга за своїми можливостями еквівалентна машині Поста та нормальним алгоритмам Маркова.

Машина Тьюринга складається з каретки (зчитує і записує головки) і нескінченної стрічки, розбитої на комірки. Кожна клітинка стрічки може містити символ з деякого алфавіту A = (a 0, a 1, ..., a N). Будь-який алфавіт містить символ пробілу, який позначається як a 0 або Λ. При введенні команд пропуск замінюється знаком підкреслення «_».

Машина Тьюринга – це автомат, який керується таблицею. Рядки в таблиці відповідають символам обраного алфавіту A, а стовпці - станам автомата Q = (q 0, q 1, ..., q M). На початку роботи машина Тьюринга перебуває у стані q1. Стан q 0 це кінцевий стан: потрапивши в нього, автомат закінчує роботу.

У кожній клітині таблиці, що відповідає деякому символу a i і деякому стану q j знаходиться команда, що складається з трьох частин:

1. символ з алфавіту A;
2. напрямок переміщення: > (вправо),
3. новий стан автомата

Новини

1. Фаліна І.М.Тема «Машина Тьюринга» у шкільному курсі інформатики (inf.1september.ru).
2. Майєр Р.В.Машини Поста та Тьюринга (komp-model.narod.ru).
3. Пильщиков В.М., Абрамов В.Г., Виліток А.А., Гаряча І.В.Машина Тьюринга та алгоритми Маркова. Вирішення завдань, М.: МДУ, 2006.
4. Бекман І.М.Комп'ютерні науки. Лекція 7. Алгоритми (profbeckman.narod.ru)
5. Соловйов А.Дискретна математика без формул (lib.rus.ec)
6. Єршов С.С.Елементи теорії алгоритмів, Челябінськ, Видавничий центр ЮУрГУ, 2009.
7. Варпахівський Ф.Л.Елементи теорії алгоритмів, М: Просвітництво, 1970.
8. Верещагін Н.К., Шень О.Обчислювані функції, М: МЦНМО, 1999.

Що з цим робити?

У верхній частині програми знаходиться поле редактора, яке можна ввести умову завдання у вільній формі.

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

За допомогою меню Стрічкаможна запам'ятати стан стрічки у внутрішньому буфері та відновити стрічку з буфера.

В полі Алфавітзадаються символи вибраного алфавіту. Пробіл автоматично додається до введених символів.

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

При введенні команди в комірку таблиці спочатку потрібно ввести новий символ, потім напрямок переходу і номер стану. Якщо символ пропущено, він не змінюється за замовчуванням. Якщо номер стану пропущено, стан автомата не змінюється.

Праворуч у полі Коментарможна вводити у довільній формі коментарі до рішення. Найчастіше там пояснюють, що означає кожен стан машини Т'юрінга.

Програма може виконуватися безперервно (F9) або кроками (F8). Команда, яка зараз виконуватиметься, підсвічується зеленим тлом. Швидкість виконання регулюється за допомогою меню Швидкість.

Завдання для машини Т'юрінга можна зберігати у файлах. Зберігається умова завдання, алфавіт, програма, коментарі та початковий стан стрічки. При завантаженні завдання з файлу та збереженні у файлі стан стрічки автоматично записується у буфер.

Якщо ви помітили помилку або у вас є пропозиції, зауваження, скарги, прохання та заяви, пишіть .

Технічні вимоги

Програма працює під управлінням операційних систем лінійки Windowsна будь-яких сучасних комп'ютерах.

Ліцензія

Програма безкоштовна для некомерційного використання. Вихідні тексти програми не розповсюджуються.

Програма поставляється « as is», тобто автор не несе жодної відповідальності за всілякі наслідки її використання, включаючи моральні та матеріальні втрати, виведення обладнання з ладу, фізичні та душевні травми.

При розміщенні програми на інших веб-сайтах посилання на першоджерело є обов'язковим.

1. 1) публікація матеріалів у будь-якій формі, у тому числі розміщення матеріалів на інших веб-сайтах;
2. 2) поширення неповних чи змінених матеріалів;
3. 3) включення матеріалів до збірників на будь-яких носіях інформації;
4. 4) отримання комерційної вигоди від продажу чи іншого використання матеріалів.

Завантаження матеріалів означає, що ви прийняли умови цієї ліцензійної угоди.

завантажити

Після розпакування архіву програма перебуває у працездатному стані та не потребує жодних додаткових установок.

Вступ

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

Обладнання машини Тьюринга надзвичайно просто, проте на ній можна виконати практично будь-яку програму. Для виконання всіх цих дій передбачена спеціальна таблиця правил, в якій прописано, що потрібно робити за різних комбінацій поточних станів і символів, прочитаних зі стрічки.

У 1947 р. Алан Т'юрінг розширив визначення, описавши "універсальну машину Тьюринга". Пізніше для вирішення певних класів завдань було введено її різновид, який дозволяв виконувати не одне завдання, а кілька.

Опис машини Тьюринга

Передісторія створення цієї роботи пов'язана з формулюванням Давидом Гільбертом на Міжнародному математичному конгресі в Парижі в 1900 невирішених математичних проблем. Однією з них була завдання доказу несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як "проблему розв'язності" - знаходження загального методу для визначення здійсненності даного висловлювання мовою формальної логіки.

Стаття Тьюринга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв'язною. Але значення статті Тьюринга виходило далеко за межі того завдання, з приводу якого вона була написана.

Наведемо характеристику цієї роботи, що належить Джону Хопкрофту: "Працюючи над проблемою Гільберта, Тьюрингу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про якийсь алгоритм, тобто процедуру, яка може бути виконана механічно, без творчості Він показав, як цю ідею можна втілити у вигляді докладної моделі обчислювального процесу. Отримана модель обчислень, в якій кожен алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названою згодом машиною Тьюринга.

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

Формально машина Тьюринга може бути описана в такий спосіб. Нехай задані:

кінцеве безліч станів - Q, у яких може бути машина Тьюринга;

кінцева множина символів стрічки - Г;

функція д (функція переходів або програма), яка задається відображенням пари з декартового твору Q x Г (машина знаходиться в стані qi та оглядає символ i) у трійку декартового твору Q х Г х (L,R) (машина переходить у стан qi, замінює символ i на символ j і пересувається вліво або вправо на один символ стрічки) - Q x Г -> Q х Г х (L,R)

один символ з Г -> е (порожній);

підмножина У є Г -> визначається як підмножина вхідних символів стрічки, причому е є (Г - У);

один із станів - q0 є Q є початковим станом машини.

Вирішувана проблема задається шляхом запису кінцевої кількості символів з множини У є Г - Si є У на стрічку:

eS1S2S3S4... ... ... Sne

після чого машина переводиться в початковий стан і головка встановлюється у самого лівого непустого символу (q0, w) -, після чого відповідно до зазначеної функції переходів (qi, Si) - - (qj, Sk, L або R) машина починає замінювати символи, що переглядаються, пересувати головку вправо або вліво і переходити в інші стани, запропоновані функцій переходів.

Зупинка машини відбувається, якщо для пари (qi,Si) функція переходу не визначена.

Алан Т'юрінг висловив припущення, що будь-який алгоритм в інтуїтивному значенні цього слова може бути представлений еквівалентною машиною Тьюринга. Це припущення відоме як теза Черча-Тьюринга. Кожен комп'ютер може моделювати машину Тьюринга (операції перезапису осередків, порівняння та переходу до іншого сусіднього осередку з урахуванням зміни стану машини). Отже, може моделювати алгоритми у будь-якому формалізмі, і з цієї тези випливає, що це комп'ютери (незалежно від потужності, архітектури тощо.) еквівалентні з погляду принципової можливості розв'язання алгоритмічних завдань.

Властивості машини Тьюринга як алгоритму

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

Дискретність. Машина Тьюринга може перейти до (к + 1) - го кроку тільки після виконання кожного кроку, тому що саме кожен крок визначає, яким буде (к + 1) - й крок.

Зрозумілість. На кожному кроці в комірку пишеться символ з алфавіту, автомат робить один рух (Л, П, Н), і машина Тьюринга перетворюється на одне з описаних станів.

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

Результативність. Змістовно результати кожного кроку і всієї послідовності кроків визначено однозначно, отже, правильно написана машина Тьюринга за кінцеве число кроків перейде у стан q0, тобто. за кінцеве число кроків буде отримано відповідь питанням завдання.

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

Транскрипт

1 Московський державний університет ім. М.В. Ломоносова Факультет обчислювальної математики та кібернетики В.М. Пильщиков, В.Г. Абрамов, А.А. Виліток, І.В. Гаряча Машина Тьюринга та алгоритми Маркова. Вирішення завдань (Навчально-методичний посібник) Москва, 2006

2 УДК ББК П32 Пильщиков В.М., Абрамов В.Г., Виліток А.А., Гаряча І.В. Машина Тьюринга та алгоритми Маркова. Вирішення задач. (Навчально-методичний посібник) – М.: МДУ, с. Видавничий відділ факультету ВМК МДУ (ліцензія ЛР від) Посібник присвячений вирішенню завдань на тему «Вступ до теорії алгоритмів», що вивчається на першому курсі факультету ВМК МДУ в рамках дисципліни «Алгоритми та алгоритмічні мови». Це завдання складання алгоритмів як машини Тьюринга і нормальних алгоритмів Маркова, і навіть завдання теоретичного характеру. У посібнику наводяться необхідні відомості з теорії алгоритмів, докладно пояснюються типові прийоми розв'язання задач та пропонується великий набір задач для самостійного розв'язання. Посібник розрахований на студентів першого курсу факультету ВМК МДУ та викладачів, які ведуть семінарські заняття з програмування. Рецензенти: доцент Баула В.Г. доцент Корухова Л.С. Друкується за рішенням Редакційно-видавничої ради факультету обчислювальної математики та кібернетики МДУ ім. М.В. Ломоносова. ISBN??? Видавничий відділ факультету обчислювальної математики та кібернетики МДУ ім. М.В. Ломоносова,

3 1. Машина Тьюринга У розділі розглядаються завдання складання алгоритмів для машини Тьюринга. Наводиться короткий опис цієї машини, на прикладах пояснюються основні прийоми складання таких алгоритмів та пропонуються завдання для самостійного вирішення. 1.1 Короткий опис машини Тьюринга Структура машини Тьюринга Машина Тьюринга (МТ) складається з двох частин стрічки та автомата (див. зліва): стрічка: a b b Λ Λ a b b Λ Λ автомат: q q Стрічка використовується для зберігання інформації. Вона нескінченна в обидві сторони і розбита на клітини, які не нумеруються і називаються. У кожній клітині може бути записано один символ або нічого не записано. Вміст клітини може змінюватися в неї можна записати інший символ або стерти символ, що знаходиться там. Домовимося порожній вміст клітини називати символом «порожньо» і позначати знаком Λ («лямбда»). У зв'язку з цим зображення стрічки, показане на малюнку праворуч, таке саме, як і малюнку зліва. Ця угода зручна тим, що операцію стирання символу в деякій клітці можна розглядати як запис в цю клітину символу Λ, тому замість довгої фрази «записати символ у клітку або стерти символ, що там знаходиться» можна говорити просто «записати символ у клітку». Автомат – це активна частина МТ. У кожний момент він розміщується під однією з клітин стрічки та бачить її вміст; це видима клітина, а символ, що знаходиться в ній, видимий символ; вміст сусідніх та інших клітин автомат не бачить. Крім того, у кожний момент автомат знаходиться в одному зі станів, які позначатимемо літерою q з номерами: q1, q2 і т.п. Перебуваючи в деякому стані, автомат виконує якусь певну операцію (наприклад, переміщається праворуч стрічкою, замінюючи всі символи b на a), перебуваючи в іншому стані іншу операцію. Пару з видимого символу (S) та поточного стану автомата (q) будемо називати конфігурацією та позначати . Автомат може виконувати три елементарні дії: 1) записувати у видиму клітинку новий символ (міняти вміст інших клітин автомат не може); 2) зрушуватися на одну клітинку вліво або вправо («перестрибувати» відразу через кілька клітин автомат не може); 3) переходити у новий стан. Нічого іншого робити автомат не вміє, тому все складніші операції так чи інакше повинні бути зведені до цих трьох елементарних дій. 3

4 Такт роботи машини Тьюринга МТ працює тактами, які виконуються один за одним. На кожному такті автомат МТ виконує три наступні дії, причому обов'язково у зазначеному порядку: 1) записує деякий символ S у видиму клітину (зокрема, може бути записаний той самий символ, що й був у ній, тоді вміст цієї клітини не змінюється); 2) зсувається однією клітину вліво (позначення L, від left), або одну клітину вправо (позначення R, від right), або залишається нерухомим (позначення N). 3) перетворюється на деякий стан q (зокрема, може залишитися у колишньому стані). Формально дії одного такту записуватимемо у вигляді трійки: S, , q де конструкція з квадратними дужками означає можливість запису в цьому місці будь-якої з літер L, R або N. Наприклад, такт *, L, q8 означає запис символу * у видиму клітинку, зрушення однією клітину вліво і перехід у стан q8. Програма для машини Т'юрінга Сама по собі МТ нічого не робить. Для того, щоб змусити її працювати, треба написати для неї програму. Ця програма записується у вигляді наступної таблиці: q 1 q j q m S 1 S 2 S i S n Λ S, , q Зліва перераховуються всі стани, в яких може знаходитися автомат, зверху всі символи (у тому числі Λ), які автомат може бачити на стрічці. (Які саме символи та стани вказувати в таблиці визначає автор програми.) На перетинах ж (у комірках таблиці) вказуються ті такти, які повинен виконати автомат, коли він перебуває у відповідному стані та бачить на стрічці відповідний символ. У цілому нині таблиця визначає дії МТ при всіх можливих конфігураціях і цим повністю задає поведінка МТ. Описати алгоритм як МТ означає пред'явити таку таблицю. (Зауваження. Часто МТ визначають як складається зі стрічки, автомата та програми, тому за різних програм виходять різні МТ. Ми ж буде вважати, в дусі сучасних комп'ютерів, що МТ одна, але вона може виконувати різні програми.) 4

5 Правила виконання програми До виконання програми потрібно виконати такі попередні дії. По-перше, треба записати на стрічку вхідне слово, до якого буде застосовано програму. Вхідне слово — це кінцева послідовність символів, записаних у сусідніх клітинах стрічки; всередині вхідного слова порожніх клітин не повинно бути, а ліворуч і праворуч від нього повинні бути тільки порожні клітини. Порожнє вхідне слово означає, що всі клітини стрічки порожні. По-друге, треба встановити автомат у стан q 1 (вказаний у таблиці першим) і розмістити його під першим символом вхідного слова: a b b q 1 Якщо вхідне слово порожнє, то автомат може дивитися будь-яку клітину, т.к. всі вони порожні. Після цих попередніх дій розпочинається виконання програми. У таблиці знаходиться комірка на перетині першого рядка (т.к. автомат знаходиться в стані q 1) і того стовпця, який відповідає першому символу вхідного слова (це необов'язково лівий стовпець таблиці), і виконується такт, зазначений у цьому комірці. В результаті автомат опиниться у новій конфігурації. Тепер такі ж дії повторюються, але вже для нової конфігурації: у таблиці знаходиться комірка, що відповідає стану і символу цієї конфігурації, і виконується такт з цієї комірки. І так далі. Коли завершується виконання програми? Введемо поняття такту зупинки. Це такт, який нічого не змінює: автомат записує у видиму клітку той самий символ, що й був у ній раніше, не зсувається і залишається у колишньому стані, тобто. це такт S,N,q для конфігурації . Потрапивши на такт зупинки, МТ, за визначенням, зупиняється, завершуючи свою роботу. У цілому нині можливі два результати роботи МТ над вхідним словом: 1) Перший результат «хороший»: це коли у якийсь момент МТ зупиняється (попадає на такт зупинки). У такому разі говорять, що МТ застосовується до заданого вхідного слова. А те слово, яке на цей момент отримано на стрічці, вважається вихідним словом, тобто. результатом роботи МТ, відповіддю. У момент зупинки повинні бути виконані наступні обов'язкові умови: усередині вихідного слова не повинно бути порожніх клітин (зазначимо, що під час виконання програми всередині слова, що обробляється, порожні клітини можуть бути, але в кінці їх вже не повинно залишитися); автомат повинен зупинитися під одним із символів вихідного слова (під яким саме не відіграє ролі), а якщо слово порожнє під будь-якою кліткою стрічки. 5

2) Другий результат «поганий»: це коли МТ зациклюється, ніколи не потрапляючи на такт зупинки (наприклад, автомат на кожному кроці зсувається вправо і тому не може зупинитися, оскільки стрічка нескінченна). І тут кажуть, що МТ незастосовна до заданого вхідного слова. Ні про який результат за такого результату не може йтися. Зазначимо, що один і той же алгоритм (програма МТ) може бути застосовним до одних вхідних слів (тобто зупинятися) і не застосовується до інших (тобто зациклюватися). Отже, застосовність/неприменимость залежить як від алгоритму, а й від вхідного слова. На яких вхідних словах алгоритм має зупинятися? На, сказати б, хороших словах, тобто. на тих, що належать до допустимих вихідних даних розв'язуваної задачі, для яких задача осмислена. Але на стрічці можуть бути записані будь-які вхідні слова, у тому числі й ті, для яких завдання не має сенсу; на таких словах поведінка алгоритму не фіксується, він може зупинитися (за будь-якого результату), а може і зациклитися. Угоди для скорочення запису Домовимося про деякі угоди, які скорочують запис програми для МТ. 1) Якщо в такті не змінюється видимий символ, або автомат не зрушується, або не змінюється стан автомата, то у відповідній позиції такту ми нічого не писатимемо. Наприклад, при конфігурації такі записи тактів еквівалентні: a,r,q3,r,q3 (але не Λ,R,q3!!) b,n,q2 b,q2 a,l,q1,l, a,n,q1, (це такт зупинка) Зауваження. Коми в тактах бажано не опускати, т.к. інакше можлива плутанина, якщо серед символів на стрічці можуть зустрітися літери L та R. 2) Якщо треба вказати, що після виконання деякого такту МТ має зупинитися, то у третій позиції цього такту писатимемо знак «!». Наприклад, такт b,l,! означає наступні дії: запис символу b у ​​видиму клітину стрічки, зсув ліворуч та зупинку. Формально вважатимуться, що у програмі МТ є стан під назвою!, в усіх осередках якого записані такти зупинки. При цьому однак такий рядок явно не виписують, а лише мають на увазі. 3) Якщо заздалегідь відомо, що в процесі виконання програми не може з'явитися деяка конфігурація, тоді, щоб підкреслити це явно, будемо у відповідному осередку таблиці малювати хрестик. (Формально цей хрестик вважається тактом зупинки.) Ці угоди необов'язкові, але скорочують запис програми і спрощують її сприйняття. 6

7 1.2 Приклади складання програм для МТ Розглянемо приклади складання програм для МТ, щоб продемонструвати деякі типові прийоми програмування на МТ. Для скорочення формулювання завдань введемо такі дві угоди: літерою Р позначатимемо вхідне слово; літерою А позначатимемо алфавіт вхідного слова, тобто. набір тих символів, у тому числі і яких може складатися Р (зазначимо, проте, що у проміжних і вихідному словах можуть з'являтися інші символи). Приклад 1 (переміщення автомата, заміна символів) А = (0,1,2,3,4,5,6,7,8,9). Нехай Р непусте слово; отже, Р це послідовність із десяткових цифр, тобто. запис невід'ємного цілого числа у десятковій системі. Потрібно отримати на стрічці запис числа, яке на 1 більше від числа Р. Рішення. Для вирішення цього завдання пропонується виконати такі дії: 1. Перегнати автомат під останню цифру числа. 2. Якщо це цифра від 0 до 8, замінити її цифрою на 1 більше і зупинитися; наприклад: Якщо ж це цифра 9, тоді замінити її на 0 і зрушити автомат до попередньої цифри, після чого таким самим способом збільшити на 1 цю передостанню цифру; наприклад: Особливий випадок: у Р лише дев'ятки (наприклад, 99). Тоді автомат зрушуватиметься вліво, замінюючи дев'ятки на нулі, і врешті-решт опиниться під порожньою кліткою. У цю порожню клітину треба записати 1 і зупинитися (відповіддю буде 100): У вигляді програми для МТ ці дії описуються наступним чином: 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 Λ,L,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 це стан, у якому автомат «біжить» під останню цифру числа. І тому він постійно рухається праворуч, не змінюючи видимі цифри і залишаючись у тому стані. Але тут є одна особливість: коли автомат знаходиться під 7

8 останньою цифрою, він ще не знає про це (адже він не бачить, що записано в сусідніх клітинах) і визначить це лише тоді, коли потрапить на порожню клітину. Тому, дійшовши до першої порожньої клітини, автомат повертається назад під останню цифру і перетворюється на стан q2 (право рухатися не треба). q2 це стан, в якому автомат додає 1 до тієї цифри, яку бачить зараз. Спочатку це остання цифра числа; якщо вона в діапазоні від 0 до 8, то автомат замінює її цифрою, яка на 1 більша, і зупиняється. Але якщо це цифра 9, то автомат замінює її на 0 і зсувається вліво, залишаючись у стані q2. Тим самим, він тепер додаватиме 1 до попередньої цифри. Якщо ця цифра дорівнює 9, то автомат замінює її на 0 і зрушується вліво, залишаючись як і у стані q2, т.к. повинен виконати те саме дію збільшити на 1 видиму цифру. Якщо ж автомат зрушив уліво, а у видимій клітці немає цифри (а є «порожньо»), то він записує сюди один і зупиняється. Зазначимо, що для порожнього вхідного слова наше завдання не визначене, тому на цьому слові МТ може поводитись як завгодно. У нашій програмі, наприклад, при порожньому вхідному слові МТ зупиняється та видає відповідь 1. Вище ми навели запис програми у повному, нескороченому вигляді. Тепер же наведемо запис програми в скороченому, більш наочному вигляді, при цьому праворуч дамо коротке пояснення дій, що реалізуються у відповідних станах автомата: q1,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 Саме так ми й надалі записуватимемо програми. Приклад 2 (Аналіз символів) А = (a, b, c). Перенести перший символ непустого слова Р у його кінець. Наприклад: a b c b b c b a Рішення. Щоб вирішити це завдання, пропонується виконати такі дії: 1. Запам'ятати перший символ слова P, а потім стерти цей символ. 2. Перегнати автомат праворуч під першу порожню клітку за P і записати в неї запам'ятований символ. Як "бігати" вправо, ми вже знаємо з попереднього прикладу. А як запам'ятати перший символ? Адже в МТ немає іншого запам'ятовуючого пристрою, крім стрічки, а запам'ятовувати символ у якійсь клітці на стрічці безглуздо: як тільки автомат зрушить вліво або вправо від цієї клітини, він забуде цей символ. Що робити? Вихід тут такий треба використовувати різні стани автомата. Якщо перший символ це a, треба перейти в стан q2, в якому автомат 8

9 біжить праворуч і записує в кінці a. Якщо ж першим був символ b, тоді треба перейти в стан q3, де робиться все те саме, тільки в кінці записується символ b. Якщо першим був символ c, тоді переходимо у стан q4, у якому автомат дописує за вхідним словом символ c. Отже, те, яким був перший символ, ми фіксуємо переведенням автомата в різні стани. Це типовий прийом під час програмування на МТ. З урахуванням сказаного програма буде такою: a b c Λ q1 Λ,R,q2 Λ,R,q3 Λ,R,q4,R, аналіз 1-го символу, видалення його, розгалуження q2,r,r,r, a,! запис a праворуч q3,r,r,r,b,! запис b праворуч q4,r,r,r,c,! запис c праворуч Розглянемо поведінку цієї програми на вхідних словах, що містять не більше одного символу. При порожньому слові, яке є «поганим» для завдання, програма зациклиться автомат, перебуваючи в стані q1 і потрапляючи весь час на порожні клітини, нескінченно переміщатиметься праворуч. (Звичайно, у цьому випадку програму можна було б зупинити, але ми спеціально зробили зациклювання, щоб продемонструвати таку можливість.) Якщо ж у вхідному слові рівно один символ, тоді автомат зітре цей символ, посунеться на одну клітинку праворуч і запише в неї цей символ : c c q1 q4! Таким чином, слово з одного символу просто зрушить на клітку праворуч. Це припустимо. Адже клітини стрічки не нумеровані, тому розташування слова на стрічці ніяк не фіксується і переміщення слова вліво або вправо помітити не можна. У зв'язку з цим не потрібно, щоб вихідне слово обов'язково знаходилося в тому ж місці, де було вхідне слово, результат може виявитися і лівіше, і правіше цього місця. Приклад 3 (порівняння символів, стирання слова) А = (a, b, c). Якщо перший і останній символи (непустого) слова Р однакові, це слово не змінювати, інакше замінити їх у порожнє слово. Рішення. Для вирішення цього завдання пропонується виконати такі дії: 1. Запам'ятати перший символ вхідного слова, не стираючи його. 2. Перемістити автомат під останній символ та порівняти його із запам'ятованим. Якщо вони рівні, більше нічого не робити. 3. Інакше знищити все вхідне слово. Як запам'ятовувати символ і як переганяти автомат під останній символ слова, ми знаємо з попередніх прикладів. Стирання ж вхідного слова реалізується 9

10 заміною всіх символів на символ Λ. При цьому, якщо автомат опинився в кінці слова, переміщатимемо автомат праворуч наліво до першої порожньої клітини. Ці дії описуються наступною програмою для МТ (нагадаємо, що хрестик у комірці таблиці означає неможливість появи відповідної конфігурації під час виконання програми): a b c q1,q2,q4,q6,! аналіз 1-го символу, розгалуження q2,r,r,r,L,q3 йти до останнього символу при 1 символі a q3,!, q8, q8 порівняти посл. символ з a, не рівні q8 (стерти P) q4,r,r,r,L,q5 аналогічно при 1-му символі b q5, q8,!, q8 q6,r,r,r,L,q7 аналогічно при 1-му символі з q7, q8, q8,! q8 Λ,L, Λ,L, Λ,L,! стерти все слово, рухаючись праворуч наліво Приклад 4 (видалення символу зі слова) А=(a,b). Видалити зі слова Р його другий символ, якщо такий є. Рішення. Здавалося б, це завдання вирішити просто: треба зрушити автомат під клітинку з другим символом і потім очистити цю клітину: Однак нагадаємо, що всередині вихідного слова не повинно бути порожніх клітин. Тому після видалення другого символу треба «стиснути» слово, перенісши перший символ однією клітинку вправо. Для цього автомат повинен повернутися до першого символу, запам'ятати його і стерти, а потім знову зрушивши вправо, записати його в клітинку, де був другий символ. Однак початковий «похід» вправо до другого символу, щоб його стерти, і подальше повернення до першого символу є зайвими діями: яка різниця переносити перший символ у порожню клітку чи клітинку з якимось символом? Тому відразу запам'ятовуємо перший символ, стираємо його і записуємо замість другого символу: a b b a b b a a b a У вигляді програми для МТ все це записується так: a b q1 Λ,R,q2 Λ,R,q3,! аналіз та видалення 1-го символу, розгалуження q2,! a,! a,! заміна 2-го символу на a q3 b,!,! b,! заміна 2-го символу на b Приклад 5 (стиснення слова) А = (a, b, c). Видалити зі слова Р перше входження символу a, якщо таке є. Рішення. У попередньому прикладі ми переносили на позицію вправо тільки один сім- 10

11 хв. В даному ж прикладі ми будемо в циклі переносити вправо всі початкові символи b і c вхідного слова до першого символу a або до порожньої клітини: Центральний момент тут як перенести символ x з лівої клітини в чергову клітинку, де знаходиться деякий символ y, щоб потім цей символ y можна було перенести до правої клітини? Якщо через q x позначити стан, у якому у видиму клітину треба записати символ x, що був раніше у клітині зліва, тоді це дію можна зобразити так: x y y z x z q x Для цього пропонується виконати такт x, r, q y, в якому об'єднані такі три дії: по- перше, у видиму клітину записується символ x, взятий із клітини зліва; по-друге, автомат зрушується праворуч під клітинку, в яку потім треба буде записати щойно замінений символ y; по-третє, автомат перетворюється на стан q y, у якому і виконуватиме цей запис. Повторення таких тактів у циклі призведе до зсуву вправо однією позицію початкових символів вхідного слова. Цей цикл повинен закінчитися, коли в черговій клітині виявиться символ a або Λ (y=a або y=λ), а на початку циклу можна вважати, що на місце першого символу зліва переноситься символ «порожньо» (x=λ). У результаті виходить наступна програма для МТ: a b c q1 Λ,R,! Λ,R,q2 Λ,R,q3,! q Λ : стерти 1-й символ і перенести його вправо q2 b,!,r, b,r,q3 b,! q b: запис b, перенесення видимого символу вправо q3 c,! c, r, q2, r, c,! q c: запис c, перенесення видимого символу вправо У цій програмі слід звернути увагу на такт Λ,R,!, який виконується в конфігурації , тобто. коли першим символом вхідного слова є a. Зрозуміло, треба просто стерти цей символ і зупинитися. Однак у цьому такті вказано ще й зрушення праворуч. Навіщо? Нагадаємо, що в момент зупинки автомат повинен перебувати під вихідним словом (під будь-яким його символом), тому ми і зрушуємо автомат із порожньої клітини на клітину з першим символом вихідного слова, який у вхідному слові був другим. b q y Приклад 6 (вставка символу слово) А=(a,b,c). Якщо Р непусте слово, то за першим символом вставити символ a. Рішення. Зрозуміло, між першим і другим символами слова Р треба звільнити клітину для нового символу a. Для цього треба перенести на одну позицію вліво.

12 перший символ (на старому місці його можна поки не видаляти), а потім, повернувшись на старе місце, записати символ a: b c a b c a b b a b a c a Перенесення символу на одну позицію вліво аналогічне перенесення символу вправо, про що йшлося у двох попередніх прикладах, тому наведемо програму для МТ без додаткових коментарів Зазначимо лише, що у станах q2, q3 і q4 автомат може бачити лише порожню клітину, а стані q5 він обов'язково бачить перший символ вхідного слова, але з порожню клітину. a b c Λ q1,l,q2,l,q3,l,q4,! аналіз 1-го символу для перенесення його вліво q2 a,r,q5 приписати a зліва q3 b,r,q5 приписати b зліва q4 c,r,q5 приписати c зліва q5,! a,! a,! замінити колишній 1-й символ a Приклад 7 (розсування слова) А = (a, b, c). Вставити P символ a за першим входженням символу c, якщо таке є. Рішення. Переглядаємо вхідне слово зліва направо до порожньої клітки або першого символу c. У першому випадку c не входить до P, тому нічого не робимо. У другому випадку треба звільнити місце для символу, що вставляється a, для чого зрушуємо початок слова P (від першого символу до знайденого символу c) на одну позицію вліво. При цьому здійснюємо такий зсув праворуч наліво від символу c до початку слова, якщо автомат знаходиться під цим символом. Крім того, щоб потім не повертатися до позиції, що звільнилася, починаємо це зрушення з запису a замість знайденого символу c. Оскільки це циклічне зрушення вліво реалізується аналогічно циклічному зсуву вправо з прикладу 5, то не пояснюватимемо його, а відразу наведемо програму для МТ: a b c q1,r,r,a,l,q4,l,! праворуч до, вставка a замість c, перенесення c вліво q2,l, a,l,q3 a,l,q4 a,! перенесення справа q3 b,l,q2,l, b,l,q4 b,! перенесення b праворуч q4 c,l,q2 c,l,q3,l,c,! перенесення c праворуч Приклад 8 (формування слова новому місці) А=(a,b,c). Видалити з P всі входження символу a. Рішення. Попередні приклади показують, що в МТ досить складно реалізуються вставки символів у слова та видалення символів зі слів. Тому іноді простіше не розсувати або стискати вхідне слово, а формувати вихідне слово.

13 в іншому, вільному місці стрічки. Саме так ми і вчинимо при вирішенні цього завдання. Саме пропонується виконати такі действия: 1. Вихідне слово будуватимемо праворуч від вхідного. Щоб розмежувати ці слова, відокремимо їх допоміжним символом, наприклад знаком =, відмінним від усіх символів алфавіту A (див. крок 1). (Нагадаємо, що на стрічці можуть бути записані не лише символи з алфавіту вхідного слова.) 2. Після цього повертаємося до початку вхідного слова (див. крок 2). a b c a b c = a b c = Тепер наше завдання перенести у циклі всі символи вхідного слова, крім a, вправо за знак = у вихідне слово, що формується. І тому аналізуємо перший символ вхідного слова. Якщо це a, тоді перемо його і переходимо до наступного символу (див. крок 3). Якщо ж перший символ це b або c, тоді перемо його і «біжимо» вправо до першої порожньої клітини (див. крок 4), куди і записуємо цей символ (див. крок 5). b c = c = c = b Знову повертаємося ліворуч до того символу, який став першим у вхідному слові, і повторюємо ті самі дії, але вже по відношенню до цього символу (див. кроки 6-9). c = b = b = b c Цей цикл завершується, коли при поверненні наліво ми побачимо як перший символ знак =. Це ознака того, що ми повністю переглянули вхідне слово і перенесли всі його символи, відмінні від a, у вихідне слово, що формується праворуч. Потрібно цей знак стерти, зрушити праворуч під вихідне слово і зупинитися (див. крок 10). = b c b c 9 10 З урахуванням всього сказаного та будуємо програму для МТ. При цьому зазначимо, що крім символів a, b і c у процесі розв'язання задачі на стрічці з'являється знак =, тому в таблиці має бути передбачений стовпець і для цього знака. a b c = q1,r,r,r,=,q2 записати праворуч знак = q2,l,l,l,l,r,q3 вліво до 1-го символу слова q3 Λ,R, Λ,R,q4 Λ, R,q5 Λ,R,! аналіз та видалення його, розгалуження q4,r,r,r,r,b,q2 запис b праворуч, повернення ліворуч (в цикл) q5,r,r,r,r,c,q2 запис c праворуч, повернення ліворуч (в цикл) 13

14 Приклад 9 (фіксування місця на стрічці) А=(a,b). Подвоїти слово P, поставивши між ним та його копією знак =. Наприклад: a a b a a b = a a b Рішення. Це завдання вирішується аналогічно попередньої: в кінець вхідного слова записуємо знак =, потім повертаємося до початку слова і в циклі всі його символи (у тому числі і a) копіюємо в порожні клітини праворуч: a a b = a a b = a a b = a 1 2 відмінність: символи копіювання вхідного слова не видаляються, і це призводить до наступної проблеми. Записавши праворуч копію чергового символу, ми потім маємо повернутися до вхідного слова у позицію цього символу і потім зрушити праворуч до наступного символу, щоб скопіювати його. Але як дізнатися, до якої позиції вхідного слова треба повернутися? Наприклад, звідки ми знаємо в прикладі, що після копіювання першого символу a ми маємо повернутися саме до першого символу вхідного слова, а чи не до другого чи третьому? У попередній задачі ми завжди поверталися до першого з символів вхідного слова, що залишилися, а тепер ми зберігаємо всі символи, тому незрозуміло, які символи ми вже скопіювали, а які ще ні. Зазначимо також, що у МТ осередки стрічки ніяк не нумеруються, немає в МТ та лічильників, які б дозволили визначити, скільки символів ми вже скопіювали. Загалом проблема, з якою ми зіткнулися, наступна: як зафіксувати на стрічці деяку позицію, в якій ми вже були і до якої пізніше маємо повернутися? Зазвичай ця проблема вирішується так. Коли ми опиняємося в цій позиції вперше, то замінюємо символ, що знаходиться в ній, на його двійник на новий допоміжний символ, причому різні символи замінюємо на різні двійники, наприклад a на A і b на B. Після цього ми виконуємо якісь дії в інших місцях стрічки. Щоб потім повернутися до нашої позиції, треба просто відшукати на стрічці ту клітинку, де знаходиться символ A або B. Потім у цій клітці можна відновити колишній символ, якщо нам більше не треба фіксувати цю позицію (саме для відновлення колишнього символу і треба було замінювати різні символи на різні двійники). Скористаємося цим прийомом у нашій задачі, виконуючи наступні дії: 1. Як уже сказано, спочатку записуємо знак = за вхідним словом (див. крок 1 вище). 2. Потім повертаємось під перший символ вхідного слова (див. крок 2 вище). 3. Далі замінюємо видимий символ a на двійник A (див. крок 3 нижче), «біжимо» вправо до першої вільної клітини та записуємо до неї символ a (див. крок 4). Після цього повертаємось ліворуч до клітини з двійником A (див. крок 5), відновлюємо колишній символ a і зрушуємо праворуч до наступного символу (див. крок 6). 14

15 a a b = A a b = A a b = a a b = a a b = a a b = a a b = a a a a b a b a a b = a a b Тепер аналогічно копіюємо другий символ (замінюємо його на A, в кінець дописуємо a і т.д.). ) та всі наступні символи вхідного слова. 4. Коли ми скопіюємо останній символ вхідного слова і повернемося до його двійника (після кроку 12), потім після зсуву однією позицію вправо ми потрапимо на знак = (крок 13). Це сигнал, що вхідне слово повністю скопійоване, тому роботу МТ треба завершувати. З урахуванням всього сказаного отримуємо таку програму для МТ: a b = A B q1,r,r,=,L,q2 поставити = праворуч від слова q2,l,l,r,q3 ліворуч під 1-й символ q3 A,R, q4 B,R,q5,! аналіз та заміна чергового символу q4,r,r,r,a,q6 запис a праворуч q5,r,r,r,b,q6 запис b праворуч q6,l,l,l,a,r,q3 b,r, q3 повернення, відновлення, до слід. символу Зазначимо, що в цій програмі можна позбавитися стану q6, якщо об'єднати його зі станом q2, передбачивши в q2 повернення вліво як до порожньої клітини, так і до символів A і B: a b = A B Λ... q2,l,l ,l, a,r,q3 b,r,q3,r,q3 ліворуч до Λ, A чи B Завдання самостійного решения Зауваження: 1) У завданнях розглядаються лише цілі неотрицательные числа, а то й сказано інше. 2) Під «одиничною» системою числення розуміється запис невід'ємного цілого числа за допомогою паличок має бути виписано стільки паличок, якою є величина числа; наприклад: 2, 5, 0<пустое слово>. 1.1 A = (a, b, c). Приписати ліворуч до слова P символ b (P bp). 1.2 A = (a, b, c). Приписати праворуч до слова P символи bc (P Pbc). 1.3 A = (a, b, c). Замінити на a кожен другий символ у слові P. 15

16 1.4 A = (a, b, c). Залишити у слові P лише перший символ (порожнє слово не змінювати). 1.5 A = (a, b, c). Залишити у слові P лише останній символ (порожнє слово не міняти). 1.6 A = (a, b, c). Визначити, чи P словом ab. Відповідь (вихідне слово): слово ab якщо є, або порожнє слово інакше. 1.7 A = (a, b, c). Визначити, чи входить слово P символ a. Відповідь: слово з одного символу a (так, входить) або пусте слово (ні). 1.8 A = (a, b, c). Якщо до слова P не входить символ a, то замінити P всі символи b на с, інакше як відповіді видати слово з одного символу a. 1.9 A = (a, b, 0,1). Визначити, чи слово P є ідентифікатором (непустим словом, що починається з літери). Відповідь: слово a (так) чи порожнє слово (ні) A=(a,b,0,1). Визначити, чи є слово P записом числа у двійковій системі числення (непустим словом, що складається лише з цифр 0 та 1). Відповідь: слово 1 (так) чи слово A=(0,1). Вважаючи непусте слово P записом двійкового числа, видалити з нього незначні нулі, якщо є A=(0,1). Для непустого слова P визначити, чи є записом ступеня двійки (1, 2, 4, 8,) в двійковій системі числення. Відповідь: слово 1 (є) або слово A=(0,1,2,3). Вважаючи непусте слово P записом числа в четвірковій системі числення, визначити, є воно парним чи ні. Відповідь: 1 (так) або A = (0,1). Вважаючи непусте слово P записом числа в двійковій системі, одержати двійкове число, що дорівнює вчетверному числу P (наприклад:) A = (0,1). Вважаючи непусте слово P записом числа в двійковій системі, одержати двійкове число, що дорівнює неповному частці від розподілу числа P на 2 (наприклад:) A=(a,b,c). Якщо P слово парної довжини (0, 2, 4,), видати відповідь a, інакше порожнє слово A=(0,1,2). Вважаючи непусте слово P записом числа в трійковій системі числення, визначити, чи воно є парним числом чи ні. Відповідь: 1 (так) або 0. (Примітка: у парній потрійній кількості має бути парна кількість цифр 1.) 1.18 A=(a,b,c). Нехай P має непарну довжину. Залишити P лише середній символ A=(a,b,c). Якщо слово P має парну довжину, залишити у ньому лише ліву половину A=(a,b,c). Приписати ліворуч до непустого слова P його перший символ. 16

17 1.21 A = (a, b). Для непустого слова P визначити, чи входить у нього вкотре його перший символ. Відповідь: a (так) чи порожнє слово A=(a,b). У непустому слові P поміняти місцями перший і останній символи A=(a,b). Визначити, є P паліндромом (перевертачем, симетричним словом) чи ні. Відповідь: a (так) чи порожнє слово A=(a,b). Замінити P кожне входження a на bb A = (a, b, c). Замінити P кожне входження ab на c A = (a, b). Подвоїти слово P (наприклад: abb abbabb) A = (a, b). Подвоїти кожен символ слова P (наприклад: bab bbaabb) A = (a, b). Перевернути слово P (наприклад: abb bba) A=(0,1). Вважаючи непусте слово P записом двійкового числа, одержати це число, але в четверичной системі. (Примітка: врахувати, що у двійковому числі може бути непарна кількість цифр.) 1.30 A=(0,1,2,3). Вважаючи непусте слово P записом числа у четвірковій системі числення, отримати запис цього числа в двійковій системі A=(0,1,2). Вважаючи непусте слово P записом позитивного числа у трійковій системі числення, зменшити це число на A=( ). Вважаючи слово P записом числа в одиничній системі числення, отримати запис цього числа в троїчній системі. (Рекомендація: слід у циклі видаляти з «одиничного» числа по паличці і щоразу додавати 1 до трійного числа, яке спочатку покласти рівним 0.) 1.33 A=(0,1,2). Вважаючи непусте слово P записом числа в трійковій системі числення, отримати запис цього числа в одиничній системі Нехай слово P має такий вигляд: (... (... n m де один із знаків +, /, або, ліворуч від якого вказано n паличок , а праворуч m паличок Реалізувати відповідну операцію в одиничній системі числення (як відповідь видати слово, вказане праворуч від стрілки): а) додавання: (... + (... (... (n 0, m 0)) n m n+ m б) віднімання: (... (... (... (... (n m 0)) n m n m в) множення) (... (... (... (... (n 0, m 0)) n m n m г)) розподіл націло: ((... /... (... (n 0, m>0, k=n div m) n m k д) взяття залишку: (... (... (... (n 0, m>0, k=n mod m) n m k 17

18 е) максимум: (... (... (... (n 0, m 0, k=max(n,m)) n m k ж) мінімум: (... (... (... (... (n 0, m 0, k = min (n, m)) k n m 1.35 A = ( ) Вважаючи слово P записом числа в одиничній системі, визначити, чи є це число ступенем 3 Відповідь: порожнє слово, якщо є, або слово з однієї палички інакше A=( ). n (n=0, 1, 2,) в одиничній системі.Отримати в цій же системі число n Нехай P має вигляд Q+R, де Q і R непусті слова із символів 0, 1 і 2. Трактуючи Q і R як записи чисел у трійковій системі числення (можливо, з незначними нулями), видати як відповідь запис суми цих чисел у тій же трійковій системі Нехай P має вигляд Q R, де Q та R непусті слова із символів 0, 1 та 2. Трактуючи Q та R як запису чисел у трійковій системі числення (можливо, з незначними нулями) і вважаючи, що Q R, видати як відповідь запис різниці цих чисел у тій же трійковій системі Нехай P має вигляд Q=R, де Q і R будь-які слова із символів a та b. Видати відповідь a, якщо слова Q і R однакові, і порожнє слово інакше Нехай P має вигляд Q=R, де Q і R непусті слова із символів 0 і 1. Трактуючи Q та R як записи двійкових чисел (можливо, з незначними нулями) , видати як відповідь слово 1, якщо ці числа рівні, і слово 0 інакше Нехай P має вигляд Q>R, де Q і R непусті слова із символів 0 і 1. Трактуючи Q і R як записи двійкових чисел (можливо, з незначними нулями), видати як відповідь слово 1, якщо число Q більше числа R, і слово 0 інакше A = ((,)). Визначити, чи збалансоване слово P за круглими дужками. Відповідь: Д (так) або Н (ні) A = (a, b). Якщо P символів a більше, ніж символів b, видати відповідь a, якщо символів a менше символів b, видати відповідь b, інакше як відповіді видати порожнє слово. 2. Нормальні алгоритми Маркова У розділі розглядаються завдання складання нормальних алгоритмів Маркова. Наводиться короткий опис цих алгоритмів, на прикладах пояснюються основні прийоми їхнього складання та пропонуються завдання для самостійного вирішення. 18

19 2.1 Короткий опис нормальних алгоритмів Маркова Підстановки Цікавою особливістю нормальних алгоритмів Маркова (НАМ) є те, що в них використовується лише одна елементарна дія так званої підстановки, яка визначається таким чином. Формулою підстановки називається запис виду α β (читається «α замінити на β»), де α та β будь-які слова (можливо, і порожні). При цьому α називається лівою частиною формули, а β правою частиною. Сама підстановка (як дія) задається формулою підстановки і застосовується до деякого слова Р. Суть операції зводиться до того, що в слові Р знаходиться частина, що збігається з лівою частиною цієї формули (тобто з α), і вона замінюється на праву частину формули (тобто на β). При цьому інші частини слова Р (ліворуч і праворуч від α) не змінюються. Слово R, що вийшло, називають результатом підстановки. Умовно це можна зобразити так: P x α y R x β y Необхідні уточнення: 1. Якщо ліва частина формули підстановки входить у слово Р, то кажуть, що ця формула застосовна до Р. Але якщо α не входить до Р, то формула вважається не застосовується до Р, і підстановка не виконується. 2. Якщо ліва частина α входить до Р кілька разів, то на праву частину β, за визначенням, замінюється лише перше входження α до Р: P x α y α z R x β y α z 3. Якщо права частина формули підстановки порожнє слово , то підстановка α зводиться до викреслювання частини α з Р (зазначимо принагідно, що у формулах підстановки не прийнято позначати порожнє слово): P x α y R x y 4. Якщо в лівій частині формули підстановки зазначено порожнє слово, то підстановка β зводиться, за визначенням, до приписування ? зліва до слова P: P x R ? Зазначимо також, що формула з порожніми лівою та правою частинами не змінює слово. Визначення НАМ Нормальним алгоритмом Маркова (НАМ) називається порожній кінцевий упорядкований набір формул підстановки: 19

20 α1 β1 α 2 β 2... (k 1) α k β k У цих формулах можуть використовуватися два види стрілок: звичайна стрілка () та стрілка «з хвостиком» (a). Формула зі звичайною стрілкою називається звичайною формулою, а формула зі стрілкою з хвостиком заключною формулою. Різниця між ними пояснюється трохи нижче. Записати алгоритм як НАМ означає пред'явити такий набір формул. Правила виконання НАМ Насамперед задається деяке вхідне слово Р. Де саме воно записано не важливо, в НАМ це питання не обговорюється. Робота НАМ зводиться до виконання послідовності кроків. На кожному кроці формули, що входять в НАМ, підстановки проглядаються зверху вниз і вибирається перша з формул, застосовних до вхідного слова Р, тобто. найвища з тих, ліва частина яких входить у Р. Далі виконується підстановка згідно знайденою формулою. Виходить нове слово Р. На наступному кроці це слово Р береться за вихідне і щодо нього застосовується та сама процедура, тобто. формули знову проглядаються зверху вниз починаючи з верхньої і шукається перша формула, застосовна до слова Р, після чого виконується відповідна підстановка і виходить нове слово Р. І так далі: Р Р Р Слід звернути особливу увагу на той факт, що на кожному кроці формули у НАМ завжди проглядаються починаючи з найпершої. Необхідні уточнення: 1. Якщо на черговому кроці було застосовано звичайну формулу (αβ), то робота НАМ триває. 2. Якщо ж на черговому кроці було застосовано заключну формулу (α a β), то після її застосування робота НАМ припиняється. Те слово, що у цей момент, і є вихідне слово, тобто. результат застосування НАМ до вхідного слова. Як видно, різниця між звичайною та заключною формулами підстановки проявляється лише в тому, що після застосування звичайної формули робота НАМ продовжується, а після заключної формули припиняється. 3. Якщо на черговому кроці до поточного слова не застосовується жодна формула, то й у цьому випадку робота НАМ припиняється, а вихідним словом вважається поточне слово. Таким чином НАМ зупиняється з двох причин: або була застосована заключна формула, або жодна з формул не підійшла. Те й інше вважається «хорошим» закінченням роботи НАМ. В обох випадках говорять, що НАМ застосовується до вхідного слова. 20

Московський державний університет імені М.В. Ломоносова Факультет обчислювальної математики та кібернетики В.М. Пильщиков, В.Г. Абрамов, А.А. Виліток, І.В. Гаряча Машина Тьюринга та алгоритми Маркова.

МАШИНА ТЬЮРІНГУ У ВИВЧЕННІ ТЕОРІЇ АЛГОРИТМІВ Лебедєва Н.Ю. Шуйська філія Іванівського державного університету TURING MACHINE IN THE STUDY THE THEORY OF ALGORITHMS Lebedeva N. Yu. Shuya branch

ДОДАТОК Додати 1 до числа означає отримати число, наступне за даними: 4+1=5, 1+1=14 і т.д. Скласти числа 5 і отже додати до 5 тричі одиницю: 5+1+1+1=5+=8. ВІДРАХУВАННЯ Відняти 1 з числа означає

Завдання та рішення відбірного туру олімпіади ДМІТІ 2014-2015 Всі завдання, маніпулятори та рішення доступні учасникам на сайті олімпіади. Усі запропоновані завдання оцінювалися однаковою кількістю балів. Графи.

Машина Тьюринга 1 Машина Тьюринга математичне поняття, а чи не реальна обчислювальна машина. МТ є математичною моделлю обчислювального пристрою. MT була запропонована Аланом Тюрінгом в 1936

Вирішення задач по машині тьюрингу онлайн >>> Розв'язання задач по машині тьюрингу онлайн Вирішення задач по машині тьюрингу онлайн Вміст клітини може змінюватися в неї можна записати інший символ або стерти

Системи числення В наш час людина постійно стикається з числами. Всі ми з дитинства знайомі із загальноприйнятим записом чисел за допомогою арабських цифр. Однак цей спосіб запису використовувався далеко не

Реалізований алгоритм Ми використовуємо наступну варіацію алгоритму Евкліда для обчислення НОД чисел M та N:. a M, b N; 2. ta-b, якщо t = 0, зупинка; 3. a t, b min(a,b), перехід на крок 2. Після зупинки НОД(M,N)

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

Глава B. Комп'ютерна арифметика Урок B3. Двійкова арифметика Подивимося, як ви впоралися із вправами з Уроку B2. Ось їхнє рішення. Вправи B2-2 a) Таблиця розміщення гир виглядає так: у нумерації

Заняття 23 В умовах задач M, x означають відповідно опис машини Тьюринга та вхідного слова у тому форматі, який був введений на лекції (і написаний у чернетці підручника). Завдання 23.1. Доведіть, що

Розділ 6. Теорія алгоритмів. Неформальне поняття алгоритму, його основні риси та властивості. Алфавіту, слова, алгоритм в алфавіті. Цілком еквівалентні алгоритми. Визначення нормального алгоритму (алгоритма

ПОЗИЦІЙНІ СИСТЕМИ ЗЛІЧЕННЯ Відомо безліч способів представлення чисел. У будь-якому випадку, число зображується символом або групою символів (словом) деякого алфавіту. Будемо називати такі символи

Завдання для 11 класу Відбірковий етап. Перший тур 1. Кодування інформації. Системи числення (2 бали) [Перестановки] Скільки існує трирозрядних шістнадцяткових чисел, для яких будуть одночасно

Вирішення задач на тему «Подання чисел у комп'ютері» Типи задач: 1. Цілі числа. Подання чисел у форматі з фіксованою комою. 2. Дробові числа. Подання чисел у форматі з плаваючою комою.

1. Лицарі та брехуни. Логічна схема - 1. Завдання та рішення очного туру Олімпіади Дмитро-2017-2018 За круглим столом сидять чотири особи. Кожен із них або лицар, або брехун. Лицарі завжди говорять тільки

Система числення Система числення спосіб запису чисел за допомогою заданого набору спеціальних символів (цифр). У обчислювальній техніці застосовуються позиційні системи числення, у яких значення цифри

ЛЕКЦІЯ 3. Алгоритми обробки одновимірних масивів. Ціль лекції: Знайомство з поняттям масиву. Набуття навичок побудови алгоритмів призначених для обробки одновимірних масивів. 6. Алгоритми

Демонстраційний варіант ЄДІ 2019 завдання 6 На вхід алгоритму подається натуральне число N. Алгоритм будує по ньому нове число R наступним чином. 1) Будується двійковий запис числа N. 2) До цього запису

Введення у системи числення А.А. Виліток Система числення - це спосіб запису чисел за допомогою заданого набору спеціальних знаків (цифр). Існують позиційні та непозиційні системи числення. У непозиційних

Частина III Мови, граматики, автомати 137 Глава 10 Мови і кінцеві автомати 10.1 Мова Дика Як відомо, правильні скобочные структури перераховуються числами Каталана. Випишемо всі правильні дужкові

Муніципальний етап всеросійської олімпіади школярів з інформатики Москва, грудня 0 р. Завдання для 7-8 класів Кожне завдання оцінюється в 0 балів. Підсумковий бал виставляється як сума балів за завдання

Віртуальні машини Введення Понад сорок лот тому видатний американський математик Еміль Л. Пост опублікував у «Журналі символічної логіки» статтю «Фінітні комбінаторні процеси, формулювання!» (її

Югорський фізико-математичний ліцей ВП Чуваков Завдання С6 (Теорія чисел на ЄДІ) Навчально-методичний посібник Ханти-Мансійськ 0 ВП Чуваков Завдання С6 (Теорія чисел на ЄДІ): Навчально-методичний посібник, - Ханти-Мансійськ,

9 КЛАС 1. В одній із клітин нескінченного картатого паперу знаходиться робот, якому можуть бути віддані наступні команди: вгору (робот переміщається на сусідню клітину зверху); вниз (робот переміщається на

Системи числення Система числення це спосіб запису чисел за допомогою заданого набору спеціальних знаків (цифр). Існують позиційні та непозиційні системи числення. У непозиційних системах вага

Системи числення Система числення спосіб опису чисел за допомогою знаків певного алфавіту за відомими правилами. Позиційні системи числення У позиційній системі числення значення цифри залежить

К. Поляков, 009-06 6 (базовий рівень, час 4 хв) Тема: Пошук алгоритму мінімальної довжини для виконавця. Що потрібно знати: виконавець це людина, група людей, тварина, машина чи інший об'єкт,

Лекція 5 Основи представлення інформації у цифрових автоматах Позиційні системи числення Системою числення називається сукупність прийомів і правил записи чисел цифровими знаками. Будь-яка призначена

Елементи теорії складності Машина Т'юрінга Алан Т'юрінг (23.06.1912-7.06.1954) (Alan Mathison Turing) Англійський математик, логік, криптограф. У 1936 році запропонував абстрактну обчислювальну «Машина Тьюринга»,

Міністерство освіти і науки Російської Федерації Державна освітня установа професійної освіти Російської Федерації «Ростовський державний університет» М. Е. Абрамян

10 КЛАС 1. Дійсні числа задовольняють співвідношенням: Знайдіть усі можливі трійки чисел, де Розв'язання. Зауважимо, що Позначимо та віднімаючи один з одного ці рівності, отримаємо Припустимо, що всі

Додаток до статті Горбунов К.Ю., Любецький В.А. «Лінійний алгоритм мінімальної перебудови структур» Доказ леми 3. Жорстким назвемо блок, обмежений з обох сторін загальними генами, напівжорстким

Додаток 1 Практикум до глави 2 «Подання інформації на комп'ютері» Практична робота до п. 2.1 Приклад 2.1. Подайте у вигляді розкладання за ступенями основи числа 2466,675 10, 1011,11 2. Для десяткового

Заочний фізико-математичний ліцей «Авангард» О. Н. Філатов АЛГЕБРА 8 Експериментальний підручник Частина 1 МОСКВА 2016 ЗМІСТ 1. Щільність. 2. Чіт непар 3. Безліч. 4. Смішні завдання. 5. Комбінаторика

Задачник з інформатики учня (ци) 11 фізико-математичного класу середньої школи 36 р. Володимира Частина II 2016-2017 р. 2 1. Алгоритмізація. 1.1 Пропонується деяка операція над двома довільними

Тема 7. Подання інформації в ЕОМ. Одиниці інформації. Біт - (bit-biry digit - двійковий розряд) найменша одиниця інформації - кількість її, необхідне розрізнення двох рівноймовірних подій.

І. В. Яковлєв Матеріали з математики MathUs.ru Зміст Десятковий запис 1 Всеросійська олімпіада школярів з математики................ 1 2 Московська математична олімпіада......... ...............

Тема 1: Системи лінійних рівнянь А. Я. Овсянніков Уральський федеральний університет Інститут математики та комп'ютерних наук кафедра алгебри та дискретної математики алгебра та геометрія для фізиків-інженерів

Глава 5 Елементи теорії алгоритмів 31 Уточнення поняття алгоритму Ключові слова: алгоритм теорія алгоритмів універсальний виконавець машина Тюрінга машина Поста нормальний алгоритм Маркова Навіщо потрібно

Вирішення задач на тему «Подання чисел у комп'ютері». Типи завдань. 1. Цілі числа. Подання чисел у форматі з фіксованою комою. 2. Дробові числа. Подання чисел у форматі з плаваючою

А. Шень Ігри та стратегії з точки зору математики, МЦНМО Прості ігри та класифікація позицій На столі лежить 12 сірників. Гравці по черзі можуть взяти від одного до трьох сірників. Хто не може зробити хід

Теорія алгоритмів 79 3.2. Нормальні алгоритми j Нехай A алфавіт, який не містить символів. в. Звичайною формулою підстановок називається запис виду P Q, де P і Q деякі слова в алфавіті A. Заключною

ЛЕКЦІЯ 2. Алгоритми циклічної структури. Мета лекції: Знайомство з поняттям алгоритму циклічної структури. Придбання навичок побудови алгоритмів циклічної структури. 5. Алгоритми циклічної

Лекції з математики. Вип. ТММ-1 Ю. В. Чебраков ТЕОРІЯ МАГІЧНИХ МАТРИЦЬ Санкт-Петербург, 2010 УДК 511+512 ББК 22 Ч345 Рецензенти: Доктор фізико-математичних наук, професор С.-Петерб. техн.

Практична робота. Форми подання числової інформації на комп'ютері. Частина I. Системи числення. Під системою числення розуміється спосіб подання будь-якого числа за допомогою деякого алфавіту

Московський фізико-технічний інститут Факультет інновацій та високих технологій Математична логіка та теорія алгоритмів, осінь 2018 Семінар 1: мова запису формальних тверджень, з рішеннями деяких

Лекція 16. Універсальна машина Тьюринга Дискретна математика, ВШЕ, факультет комп'ютерних наук (Осінь 2014 року весна 2015) Найважливішою властивістю функцій, що обчислюються, є існування універсальної обчислюваної

16 (підвищений рівень, час хв) Тема: Кодування чисел. Системи числення. Що потрібно знати: принципи кодування чисел у позиційних системах числення, щоб перевести число, скажімо, 15, із системи

2015 Регулярні вирази Розв'язання задач відбірного туру (два варіанти) Варіант 1 Побудуйте регулярний вираз, що описує безліч слів з літер a та b, з якого видалені всі слова, які задаються регулярним виразом.