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

слайд 2

Вступ

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

слайд 3

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

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

слайд 4

Стрічка

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

слайд 5

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

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

слайд 6

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

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

слайд 7

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

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

слайд 8

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

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

слайд 9

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

слайд 10

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

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

слайд 11

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

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

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

Алан Тьюринг

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

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

Машина Тьюринга Протягом декількох тижнів після прибуття в Блетчлі-парк Тьюринг написав специфікації до електромеханічної машині, яка могла допомогти зі зломом «Енігми» більш ефективно, ніж польська «криптологічну бомба». Машина Тьюринга з поліпшеннями, запропонованими математиком Гордоном Велшманом, стала найважливішим інструментом для розшифровки повідомлень «Енігми». Машина отримала назву Bombe. Машина шукала можливі настройки, використані для шифрування повідомлень (порядок роторів, положення ротора, сполуки комутаційної панелі), спираючись на відомий відкритий текст. Для кожної можливої \u200b\u200bналаштування ротора (у якого було 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, який сьогодні використовується для вирішення рівнянь.