Алгоритмічні машини презентація. машина Тьюринга

Методична розробка уроку, про який піде мова в даній публікації, призначена для вивчення в 10 класі при розгляді тематичного блоку « Алгоритм. виконавці алгоритму».

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

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

Опис ходу заняття про машину Тьюринга

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

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

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

Що називають алгоритмом і кому він призначається?

Якими властивостями володіє алгоритм?

Хто здатний постати в якості виконавця алгоритму?

Назвіть основні поняття машини Тьюринга.

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

Приклади машин Тьюринга - теоретична частина

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

1) стрічка необмежена і розділена на осередки;
2) керована програмою головка, яка зчитує інформацію і іменована автоматом.

Замінити міститься в доступній для огляду осередку пам'яті одну букву алфавіту на іншу;

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

Змінити власний внутрішній стан.

Рішення задач за допомогою машин Тьюринга

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

Завдання 1. Стрічка машини Тьюринга містить деякий десяткове число. Необхідно додати до цього числа 1 ( одиницю). Автомат в даному випадку оглядає якусь цифру, відповідну вхідного числа.

Визначення машини Тьюринга

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

Структура і опис машини Тьюринга Машина Тьюринга складається з: нескінченної стрічки, розділеної на комірки; каретки (читаючої і записуючої головки); програмованого автомата (програма у вигляді таблиці). Автомат кожен раз "бачить" тільки одну клітинку. Залежно від того, яку букву він бачить, а також в залежності від свого стану q автомат може виконувати наступні дії: записати нову букву в оглядається осередок; виконати зрушення по стрічці на одну клітинку вправо / вліво або залишитися нерухомим; перейти в новий стан.

1) Зовнішній алфавіт А = (a 0, a 1, ..., a n) Елемент a 0 називається порожній символ або порожня буква (ознака того, що осередок порожня). У цьому алфавіті у вигляді слова кодується вихідний набір даних і результат роботи алгоритму. Пристрій машини Тьюринга

2) Внутрішній алфавіт Q = (q 0, q 1, ..., qm), (П, Л, Н!) В будь-який момент часу машина Тьюринга знаходиться в одному з станів q 0, q 1, ..., qm При цьому: q 1 - початковий стан (машина починає роботу) q 0 - заключне стан (машина закінчила роботу) символи (П, Л, Н!) - символи зсуву (вправо, вліво, на місці) Пристрій машини Тьюринга

Види команд машини Тьюринга Написати нову букву в оглядається осередок Виконати зрушення по стрічці на одну клітинку вправо / вліво або залишитися на місці (П, Л, Н) Перейти в новий стан. а 0 а 1 ... а i ... а j q 0 q 1 ... a k (ЛПН) q m q i ... q j 1 1 1 * 1 1 Вказівка ​​про зміну символу Вказівка ​​про зрушення каретки Вказівка ​​про зміну внутрішнього стану

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

3) Зовнішня пам'ять (стрічка) Пристрій машини Тьюринга Порожня клітка містить a 0. У кожен момент часу на стрічці записано кінцеве число непустих букв Стрічка є кінцевою, але доповнюється в будь-який момент осередками зліва і справа для запису нових непустих символів. Це відповідає принципу абстракції потенційної здійсненності

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

5) Функціональна схема (програма) Програма машини складається з команд: Пристрій машини Тьюринга Для кожної пари (q i, a j) програма машини повинна містити одну команду (детермінована машина Тьюринга)

До початку роботи машини на стрічку подається вихідний набір даних у вигляді слова  Опис роботи машини Тьюринга Будемо говорити, що непорожнє слово  в алфавіті А \ (a 0) сприймається машиною в стандартному положенні, якщо: - воно задано в послідовних комірках стрічки, - всі інші осередки порожні, - машина оглядає крайню праву осередок з тих, в яких записано слово 

Опис роботи машини Тьюринга Стандартне положення називається початковим (заключним), якщо машина, яка сприймає слово в стандартному положенні, знаходиться в початковому стані q 1 (стоп-стані q 0)

Перебуваючи в не останню стані, машина робить крок, який визначається поточним станом q i і розглядаємим символом a j Опис роботи машини Тьюринга

Опис роботи машини Тьюринга Відповідно до командою qiaj  qkal Х виконуються наступні дії: 1) Вміст оглядається осередку aj стирається і в неї записується символ al (який може збігатися з aj) 2) Машина переходить в новий стан qk (воно може збігатися зі станом qi) 3) Каретка переміщається відповідно до керованим символом Х  (П, Л, Н!)

При переході машини в заключне стан q 0 її робота припиняється На стрічці записаний результат роботи алгоритму - слово  в алфавіті А \ (a 0) Опис роботи машини Тьюринга

Машинним словом (конфігурацією) машини Тьюринга називається слово виду  1 q k a l  2, де  1 і  2 - слова в алфавіті А.

Конфігурація  1 q k a l  2 інтерпретується наступним чином: - машина знаходиться в стані q k - каретка оглядає на стрічці символ a l -  1 і  2 - це вміст стрічки до і після символу a l

Ситуації незастосовності машини Тьюринга Вважається, що машина Тьюринга непридатна до даного вхідному слову, якщо в програмі немає клітин зупинки або машина в процесі роботи на них не потрапляє. Наприклад: Машина Тьюринга може бути застосована до даного вхідному слову, якщо, почавши роботу над цим вхідним словом, вона рано чи пізно дійде до однієї з клітин зупинки. Як змінилася програма в прикладі? а 0 0 1 q 1 1П q 1 0П q 1 1П q 1 а 0 0 1 q 1 1Н q 0 0П q 1 1П q 1

Приклад машин Тьюринга Потрібно побудувати машину Тьюринга для вирішення наступного завдання: у вхідному слові всі букви «а» замінити на букви «б» і навпаки. а 0 а б в ... я q 1 а 0 Н! б Л q 1 а Л q 1 в Л q 1 ... я Л q 1 у  у б  а а  б р  р у б а р о б а  б б  а а б б а

Реалізуйте запропонований алгоритм Машина Тьюринга додає одиницю до числа на стрічці. Вхідний слово складається з цифр цілого десяткового числа, Записаного в послідовні комірки на стрічці. У початковий момент машина знаходиться проти самої правої цифри числа. а 0 0 1 2 3 4 ... 7 8 9 q 1 1Н q 0 1Н q 0 2Н q 0 3Н q 0 4Н q 0 5Н q 0 ... 8Н q 0 9Н q 0 0л q 1

Реалізуйте запропонований алгоритм На стрічці машини Тьюринга міститься послідовність символів «+». Машина Тьюринга кожен другий символ «+» замінює на «-». Заміна починається з правого кінця послідовності. Автомат в стані q 1 оглядає один із символів зазначеної послідовності. а 0 + - q 1 а 0 Л q 2 + П q 1 q 2 а 0 Н! + Л q 3 q 3 а 0 Н! - Л q 2 q 1 - машина шукає правий кінець числа; q 2 - пропускає знак «+», при досягненні кінця послідовності - останов; q 3 - знак «+» замінює на «-».

Приклад Дана машина Тьюринга із зовнішнім алфавітом А = (a 0, 1, *), алфавітом внутрішніх станів Q = (q 0, q 1, q 2, q 3), і наступної функціональною схемою: Застосувати машину Тьюринга до слова  = 11 * 1, починаючи зі стандартного початкового положення

Рішення 1) Замінюємо вміст оглядається осередку 1 на а 0

Рішення 2) Машина переходить в новий стан q 2

Рішення 3) Каретка переміщається вліво

Рішення Повний докладний рішення

Рішення Повний докладний рішення

Рішення Рішення, записане за допомогою конфігурацій (в рядок)

 = 1 * 11 Відповідь:  = 111

Література Игошин В.І. Математична логіка і теорія алгоритмів. - М .: Академія, 2008. - 448 с. Ліхтарніков Л.М., Сукачова Т.Г. Математична логіка. Курс лекцій. Задачник-практикум та рішення. - СПб .: Лань, 1999. - 288 с. Ільїних А.П. Теорія алгоритмів. Навчальний посібник. - Єкатеринбург, 2006. - 149 с.

Люди можуть вести себе по-різному в однакових ситуаціях, і цим вони принципово відрізняються від машин.

Алан Тьюринг

Алан Метісон Тьюринг Алан Метісон Тьюринг (англ. Alan Mathison Turing, 23 червня 1912 - 7 червня 1954) - англійський математик, логік, криптограф, що зробив істотний вплив на розвиток інформатики. Кавалер Ордена Британської імперії (1945), член Лондонського королівського товариства (1951). Запропонована ним в 1936 році абстрактна обчислювальна «Машина Тьюринга», яку можна вважати моделлю комп'ютера загального призначення, дозволила формалізувати поняття алгоритму і до сих пір використовується в безлічі теоретичних і практичних досліджень. Наукові праціА. Тьюринга - загальновизнаний внесок у заснування інформатики (і, зокрема, - теорії штучного інтелекту).

Час Війни Під час Другої світової війни Алан Тьюринг працював в Урядовій школі кодів і шифрів, що розташовувалася в Блетчлі-парк, де була зосереджена робота по злому шифрів і кодів країн осі. Він очолював групу Hut 8, відповідальну за криптоаналіз повідомлень військово-морського флоту Німеччини. Тьюринг розробив ряд методів злому, в тому числі теоретичну базу для Bombe - машини, використаної для злому німецького шифратора Enigma.

Машина Тьюринга Протягом декількох тижнів після прибуття в Блетчлі-парк Тьюринг написав специфікації до електромеханічної машині, яка могла допомогти зі зломом «Енігми» більш ефективно, ніж польська «криптологічну бомба». Машина Тьюринга з поліпшеннями, запропонованими математиком Гордоном Велшманом, стала найважливішим інструментом для розшифровки повідомлень «Енігми». Машина отримала назву Bombe. Машина шукала можливі настройки, використані для шифрування повідомлень (порядок роторів, положення ротора, сполуки комутаційної панелі), спираючись на відомий відкритий текст. Для кожної можливої ​​налаштування ротора (у якого було 1019 станів або 1022 в модифікації, що використовувалася на підводних човнах) машина виробляла ряд логічних припущень, грунтуючись на відкритому тексті (його зміст і структуру). Далі машина визначала протиріччя, відкидала набір параметрів і переходила до наступного. Таким чином, більшість потенційних наборів відсіваються і для ретельного аналізу залишалося всього кілька варіантів. Перша машина була запущена в експлуатацію 18 березня 1940 року. Перебір ключів виконувався за рахунок обертання механічних барабанів, що супроводжувався звуком, схожим на цокання годинника.

Colossus У липні 1942 року Тьюринг взяв участь в розшифровці коду «Лоренц», що застосовувався німцями для передачі повідомлень вищого командування. «Лоренц» був істотно складніше «Енігми» і не піддавався розшифровці існували методами. Тьюринг запропонував використовувати в конструкції дешифратора електронні лампи і привів в команду Т. Флауерса - досвідченого інженера-електронщика. В результаті спільних зусиль математиків і інженерів був розроблений «Колос» - одна з перших в світі ЕОМ. До 1944 за допомогою «Колоса» код «Лоренц» був зламаний, що дозволило союзникам читати всю переписку вищого німецького керівництва. За деякими оцінками, це наблизило поразка Німеччини на кілька років

Ранні комп'ютери і тест Тьюринга З 1945 та 1947 роком Тьюринг проживав в Річмонді і працював над ACE (Automatic Computing Engine) в Національній фізичній лабораторії. 19 лютого 1946 році він представив роботу, яку можна назвати першим детальним описом комп'ютера з зберiгається в пам'ятi. Незакінчена робота "Перший проект звіту про EDVAC" (1945) Фон Неймана, передувала їй, але була набагато менш детальна, а згідно керівнику математичного відділення Національної фізичної лабораторії - Джону Воурмслей: вона містить ряд ідей, які належать доктору Тьюрингу. Незважаючи на те, що споруда ACE була цілком здійсненна, секретність, що оточувала Блетчлі-парк привела до затримок на початку робіт, що розчарувало Тьюринга. До кінця 1947 роки він повернувся в Кембридж заради річного відпустки протягом якого він плідно працював над «Intelligent Machinery», яка не була опублікована прижиттєво. Поки Алан Тьюринг перебував в Кембриджі Pilot ACE був побудований в його відсутність. Він виконав свою першу програму 10 травня 1950 року. хоча повна версія ACE ніколи не була побудована, деякі комп'ютери мали з ним багато спільного, наприклад DEUCE і Bendix G-15

У 1948 році Алан Тьюринг отримав звання Reader (англ.) В математичному департаменті Манчестерського університету (англ.). Там в 1949 році він став директором Комп'ютерної Лабораторії, де була зосереджена робота з програмування Манчестерського Марка I. У той же час Тюрінг продовжував працювати над більш абстрактними математичними завданнями, а в своїй роботі "Computing Machinery and Intelligence" (англ.) (Журнал « Mind », жовтень 1950) він звернувся до проблеми штучного інтелекту і запропонував експеримент, який став згодом відомим, як тест Тьюринга. Його ідея полягала в тому, що можна вважати, що комп'ютер «мислить», якщо людина, що взаємодіє з ним, не зможе в процесі спілкування відрізнити комп'ютер від іншої людини. У цій роботі Тьюринг припустив, що замість того щоб намагатися створити програму, що симулює розум дорослої людини, набагато простіше було б почати з розуму дитини, а потім навчати його. CAPTCHA, заснований на зворотному тесті Тьюринга, широко поширений в інтернеті. У 1948 році Алан спільно зі своїм колишнім колегою Девідом Чамперновном (англ.) Почав писати шахову програму для комп'ютера, який ще не існував. У 1952 році, не маючи відповідного пристрою для її виконання, Тьюринг зіграв гру, в якій симулював дії машини, роблячи по одному ходу раз в півгодини. Гра була записана і в результаті програма програла колезі Тьюринга Алеку Глини, але виграла партію у дружини Чамперновна. Тьюринг також винайшов метод LU-розкладання в 1948, який сьогодні використовується для вирішення рівнянь.

слайд 2

Вступ

Поняття алгоритму. Алгоритм - це точне розпорядження, що визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату (Марков А.А.) Властивості алгоритму: 1) Дискретність. 2) Визначеність. 3) Результативність. 4) Масовість.

слайд 3

Математична модель машини Тьюринга

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

слайд 4

Стрічка

В клітини в дискретний момент часу може бути записаний тільки один символ (буква) з зовнішнього алфавіту A = (, a1, a2, ..., an-1), 2≥n. Порожня клітинка позначається символом, а сам символ називається порожнім, при цьому інші символи називаються непорожніми.

слайд 5

голівки, що зчитує

Головка може зчитувати вміст комірки і записувати в неї новий символ з алфавіту А. В одному такті роботи вона може зрушуватися тільки на одну клітинку вправо (П), вліво (Л) або залишатися на місці (Н).

слайд 6

Внутрішня пам'ять

Внутрішня пам'ять машини являє собою деякий кінцеве безліч внутрішніх станів Q = (q0, q1, ..., qm), m≥ 1. Будемо вважати, що потужність | Q | ≥2. Два стану машини мають особливе значення: q1 - початкова внутрішній стан (початкових внутрішніх станів може бути кілька), q0 - заключне стан або стоп-стан (заключне стан завжди одне). У кожен момент часу МТ характеризується становищем головки і внутрішнім станом.

слайд 7

Пристрій керування

Виконує наступні дії: Змінює зчитування в момент t символ ai на новий символ aj (зокрема залишає його без змін, т. Е. Ai = aj); Пересуває голівку в одному з наступних напрямків: Н, Л, П; Змінює наявне в момент t внутрішній стан машини qi на нове qj, в якому буде машина в момент часу t +1. Такі дії пристрою управління називають командою, яку можна записати у вигляді: qiaiajDqj

слайд 8

Робота машини Тьюринга

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

слайд 9

Якщо в початковий момент на стрічці записано слово a1, a2,, a1, a1 то початкова конфігурація буде мати вигляд: Робота машини Тьюринга складається в послідовному застосуванні команд, причому, застосування тієї чи команди визначається поточною конфігурацією. Так в наведеному вище прикладі повинна застосуються команда з лівою частиною q1a1. Результатом роботи машини вважається слово, яке буде записано на стрічці в заключній конфігурації, т. Е. В конфігурації, в якій внутрішній стан машини є q0.

слайд 10

Приклади машини Тьюринга

Приклад 1. Побудувати машину Тьюринга T1, яка може бути застосована до всіх слів із зовнішнім алфавітом (a, b) і робить наступне: будь-яке слово x1, x2 ... xn, де xi = a або xi = b (i = 1, 2 ... n) перетворює в слово x2, ... xn, x1 т. е., починаючи працювати при слові x1, x2 ... xn на стрічці в початковій конфігурації, машина зупиниться, і в заключній конфігурації на деякій ділянці стрічки буде записано слово x2, ... xn, x1, а всі інші клітини стрічки (якщо такі будуть) виявляться порожніми.

слайд 11

Рішення: За зовнішній алфавіт машини T1 візьмемо безліч A = (, a, b), а за внутрішній - Q = (q0, q1, q2, q3). Команди визначимо наступним чином: q1a Пq2, q1b Пq3, qiy ППi, де yε (a, b), i = 2, 3; q2 aHq0, q3 bHq0 Розглянемо роботу машини T1 над словом ba. В роботі машини над словом ba початкова конфігурація має наступний вигляд:

Більш короткий запис цієї послідовності конфігурацій, т. Е. Процесу роботи машини буде: Таким чином, слово bbabb перероблено машиною в слово babbb.

Подивитися всі слайди