ФЕДЕРАЛЬНА АГЕНЦІЯ З ОСВІТИ ДЕРЖАВНА ОСВІТАЛЬНА УСТАНОВА ВИЩОЇ ПРОФЕСІЙНОЇ ОСВІТИ «ВОРОНІЗЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ» Т. Кацаран, Л.М. Строєва МАШИНА ТЬЮРИНГУ ТА РЕКУРСИВНІ ФУНКЦІЇ Навчальний посібник для вузів Видавничо-поліграфічний центр Воронезького державного університету 2008 р. Затверджено науково-методичною радою факультету ПММ 25 травня 2008 р., протокол № 9 Реценз. кафедри математичних методів дослідження операцій Т.М. Леденєва Навчальний посібник підготовлено на кафедрі нелінійних коливань факультету ПММ Воронезького державного університету. Рекомендується для студентів 1 курсу факультету ПММ ВДУ, Старооскольської та Ліскінської філій ВДУ. Для спеціальності 010500 – Прикладна математика та інформатика ВСТУП Слово «алгоритм» походить від algorithmi – латинського написання імені узбецького математика та астронома, що жив у VIII–IX століттях (783–850 рр.), Мухаммеда бен Муси аль-Х. Під цим ім'ям у Середньовічній Європі знали найбільшого математика з Хорезма (місто в сучасному Узбекистані). У своїй книзі «Про індійський рахунок» він сформулював правила запису натуральних чисел за допомогою арабських цифр та правила дій над ними. Потім поняття алгоритму стало використовуватися у ширшому значенні і не лише в математиці. Як математиків, так практиків поняття алгоритму має значення. Таким чином, можна сказати, що алгоритм – це точне розпорядження про виконання у певному порядку певної системи операцій для вирішення всіх завдань одного й того самого типу, що визначає послідовність дій, що забезпечує отримання необхідного результату з вихідних даних. Зауважимо, що це визначення поняття «алгоритм», лише його опис, його інтуїтивний сенс. Алгоритм може бути призначений для виконання як людиною, так і автоматичним пристроєм. Дане уявлення про алгоритм не є суворим з математичної точки зору, тому що в ньому використовуються такі поняття як «точний припис» та «вихідні дані», які, власне кажучи, суворо не визначені. Особливістю будь-якого алгоритму є його здатність вирішувати певний клас завдань. Наприклад, це може бути алгоритм вирішення систем лінійних рівнянь, знаходження найкоротшого шляху у графі тощо. Створення алгоритму, хай навіть найпростішого, – процес творчий. Він доступний виключно живим істотам, а довгий час вважалося лише людині. Інша справа - реалізація вже мають-3 гостя алгоритму. Її можна доручити суб'єкту чи об'єкту, який зобов'язаний вникати у сутність справи, а можливо, і здатний його зрозуміти. Такий суб'єкт чи об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може бути пральна машина-автомат, яка неухильно виконує запропоновані їй дії, навіть якщо ви забули покласти в неї порошок. Людина теж може виступати в ролі формального виконавця, але в першу чергу формальними виконавцями є різні автоматичні пристрої та комп'ютер у тому числі. Кожен алгоритм створюється для цілком конкретного виконавця. Ті дії, які може вчиняти виконавець, називаються його допустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен містити лише ті дії, які є допустимими для даного виконавця. Тому зазвичай формулюють кілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми з інших інструкцій. Алгоритм повинен мати такі властивості. Дискретність (перервність, роздільність) – алгоритм має представляти процес розв'язання задачі як послідовне виконання простих (чи раніше певних) кроків. Кожна дія, передбачена алгоритмом, виконується лише після того, як закінчилося виконання попереднього. Визначеність – кожне правило алгоритму має бути чітким, однозначним і залишати місця для свавілля. Завдяки цьому властивість виконання алгоритму носить механічний характер і не потребує жодних додаткових вказівок або відомостей про завдання, що розв'язується. Результативність (кінцевість) – алгоритм повинен призводити до розв'язання задачі за кінцеве число кроків. 4 Масовість – алгоритм розв'язання задачі розробляється у загальному вигляді, тобто, він має бути застосований для деякого класу задач, що відрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з певної області, яка називається областю застосування алгоритму. Теорія алгоритмів – це розділ математики, що вивчає загальні властивості алгоритмів. Розрізняють якісну та метричну теорію алгоритмів. Основною проблемою якісної теорії алгоритмів є проблема побудови алгоритму, що має задані властивості. Таку проблему називають алгоритмічною. Метрична теорія алгоритмів досліджує алгоритм із погляду їх складності. Цей розділ теорії алгоритмів відомий також як алгоритмічна теорія складності. При пошуку рішень деяких завдань довго не вдавалося знайти відповідний алгоритм. Прикладами таких завдань є: а) вказати спосіб, згідно з яким для будь-якої предикатної формули за кінцеве число дій можна з'ясувати, чи тотожна істинна вона чи ні; б) чи можна в цілих числах діофантове рівняння (алгебраїчне рівняння з цілими коефіцієнтами). Оскільки для вирішення цих задач знайти алгоритмів не вдалося, виникло припущення, що такі алгоритми взагалі не існують, що й доведено: перше завдання вирішено А. Черчем, а друге – Ю.В. Матіясевичем та Г.В. Чудновським. Довести це за допомогою інтуїтивного поняття алгоритму в принципі неможливо. Тому було зроблено спроби дати точне математичне визначення поняття алгоритму. У 1930-х років ХХ століття С.К. Кліні, А.А. Марков, Еге. Пост, А. Тюрінг, А. Черч та інші припустили різні математичні визначення 5 поняття алгоритму. Згодом було доведено, що ці різні формальні математичні визначення в певному сенсі еквіваленти: обчислюють одну й ту саму безліч функцій. Це свідчить, що, очевидно, основні риси інтуїтивного поняття алгоритму правильно відбито у цих визначеннях. Далі розглянемо математичне уточнення алгоритму, запропоноване А. Т'юрінгом, яке називають машиною Тьюринга. 6 1. МАШИНА ТЬЮРІНГА § 1. Математична модель машини Тьюринга Ідея створення машини Тьюринга, запропонована англійським математиком А. Тьюрингом у 30-х роках XX століття, пов'язана з його спробою дати точне математичне визначення поняття алгоритму. Машина Тьюринга (МТ) – це математична модель ідеалізованої цифрової обчислювальної машини. Машина Тьюринга є таким самим математичним об'єктом, як функція, похідна, інтеграл, група тощо. буд. Як і інші математичні поняття, поняття машини Тьюринга відбиває об'єктивну реальність, моделює деякі реальні процеси. Для опису алгоритму МТ зручно представляти деякий пристрій, що складається з чотирьох частин: стрічки, головки зчитування, пристрої керування та внутрішньої пам'яті. 1. Стрічка передбачається потенційно нескінченною, розбитою на комірки (рівні клітини). При необхідності до першої або останньої клітини, в якій знаходяться символи, прилаштовується порожня клітина. Машина працює в часі, який вважається дискретним, і його моменти занумеровані 1, 2, 3, … . У кожний момент стрічка містить кінцеву кількість клітин. У клітини в дискретний час може бути записаний лише один символ (літера) із зовнішнього алфавіту A = (L, a1 , a 2 ,..., a n -1 ), n ³ 2 . Пустий осередок позначається символом L, а сам символ L називається порожнім, при цьому інші символи називаються непустими. У цьому алфавіті A у вигляді слова (кінцевого впорядкованого набору символів) кодується та інформація, яка подається до МТ. Машина «переробляє» інформацію, подану у вигляді слова, у нове слово. 2. Зчитуюча головка (деякий зчитуючий елемент) переміщується вздовж стрічки так, що в кожний момент часу вона оглядає 7 рівно одну комірку стрічки. Головка може зчитувати вміст комірки та записувати в неї новий символ із алфавіту А. В одному такті роботи вона може зрушуватися лише на одну комірку вправо (П), вліво (Л) або залишатися на місці (Н). Позначимо множину переміщень (зсуву) головки D = (П, Л, Н). Якщо в даний момент часу t головка знаходиться в крайній клітині і зсувається у відсутню клітину, то прибудовується нова порожня клітина, над якою опиниться головка в момент t + 1 . 3. Внутрішня пам'ять машини є деякою кінцевою множиною внутрішніх станів Q = ( q0 , q1 , q 2 , ..., q m ), m ³ 1 . Будемо вважати, що потужність | Q | ³ 2. Два стани машини мають особливе значення: q1 – початковий внутрішній стан (початкових внутрішніх станів може бути декілька), q0 – заключний стан або стоп-стан (заключний стан завжди один). У кожний момент часу МТ характеризується положенням голівки та внутрішнім станом. Наприклад, під коміркою, над якою знаходиться головка, вказується внутрішній стан машини. ¯ a2 a1 L a2 a3 q1 4. Пристрій керування в кожний момент t залежно від символу, що зчитується в цей момент, на стрічці і внутрішнього стану машини виконує наступні дії: 1) змінює зчитуваний в момент t символ ai на новий символ a j (зокрема залишає його без змін, тобто ai = aj); 2) пересуває голівку в одному з наступних напрямків: Н, Л, П; 3) змінює наявний у момент t внутрішній стан машини 8 qi на новий q j , в якому буде машина в момент часу t +1 (можливо, що qi = q j). Такі дії пристрою управління називають командою, яку можна записати у вигляді: qi ai ® a j D q j , (1) де qi – внутрішній стан машини на даний момент; a i – символ, що зчитується в цей момент; a j – символ, який змінюється символ a i (може бути ai = a j); символ D є або Н, або Л, або П і вказує напрямок руху головки; q j – внутрішній стан машини наступного моменту (може бути qi = q j). Вирази qi ai та a j D q j називаються лівою та правою частинами цієї команди відповідно. Число команд, у яких ліві частини попарно різні, є кінцевим числом, оскільки множини Q \ (q 0 ) і A кінцеві. Не існує команд з однаковими лівими частинами, тобто якщо програма машини T містить вирази qi ai ® a j D q j і qt at ® ak D qk , то qi ¹ qt або ai ¹ at і D О (П, Л, Н). Сукупність усіх команд називається програмою машини Тьюринга. Максимальне число команд у програмі дорівнює (n + 1) Ч m, де n + 1 = A і m + 1 = Q. Вважається, що заключний стан команди q0 може стояти тільки у правій частині команди, початковий стан q1 може стояти як у лівій, так і у правій частині команди. Виконання однієї команди називається кроком. Обчислення (або робота) машини Тьюринга є послідовністю кроків одного за одним без перепусток, починаючи з першого. Отже, МТ задана, якщо відомі чотири кінцеві множини: зовнішній алфавіт A , внутрішній алфавіт Q , множина D переміщень головки і програма машини, що являє собою кінцеву множину команд. 9 § 2. Робота машини Тьюринга Робота машини повністю визначається завданням у перший (початковий) момент: 1) слова на стрічці, тобто послідовності символів, записаних у клітинах стрічки (слово виходить читанням цих символів по клітинах стрічки зліва направо) ; 2) положення головки; 3) внутрішнього стану машини. Сукупність цих трьох умов (зараз) називається конфігурацією (зараз). Зазвичай у початковий момент внутрішнім станом машини є q1 , а головка знаходиться над першою зліва, або над першою справа клітиною стрічки. Задане слово на стрічці з початковим станом q1 та положення головки над першим словом називається початковою конфігурацією. Інакше говорять, що машина Тьюринга не застосовна до початку початкової конфігурації. Іншими словами, у початковий момент конфігурація представима в наступному вигляді: на стрічці, що складається з деякого числа клітин, у кожній клітині записаний один із символів зовнішнього алфавіту A , головка знаходиться над першою ліворуч або першою справа клітиною стрічки і внутрішньою стоянням машини є q1. Слово на стрічці і положення головки, що вийшло в результаті реалізації цієї команди, називається заключною конфігурацією. Наприклад, якщо в початковий момент на стрічці записано слово a1La 2 a1a1 , то початкова конфігурація матиме вигляд: a1 a2 L a1 a1 q1 (під кліткою, над якою знаходиться головка, вказується внутрішній стан машини). 10

Тема “Машина Тьюринга” у шкільному курсі інформатики

І.М. Фаліна,
Москва

У багатьох підручниках з інформатики щодо поняття та властивостей алгоритму присутні фрази такого змісту: “...існує багато різних способів для запису одного й того ж алгоритму, наприклад, запис у вигляді тексту, запис у вигляді блок-схеми, запис на якомусь алгоритмічному мові, представлення алгоритму як машини Тьюринга чи машини Поста…”. На жаль, такого типу фрази є єдиними, де згадується машина Тьюринга. Без сумніву, обсяг годинника, що відводиться на вивчення алгоритмів, не дозволяє включати в цю тему ще й вивчення способів запису алгоритму у вигляді Тюрінгової машини. Але ця тема вкрай цікава, важлива і корисна для школярів, які особливо захоплюються інформатикою.

Тема “Машина Тьюринга” може вивчати у 8–11-х класах у рамках теми “Інформаційні процеси. Обробка інформації”, на факультативних заняттях, у системі додаткової освіти, наприклад, у школах молодих програмістів. Вивчення цієї теми може супроводжуватися комп'ютерною підтримкою, якщо вчитель має програмний тренажер-імітатор “Машина Тьюринга”. У класах із поглибленим вивченням програмування школярі можуть самостійно написати програму "Машина Тьюринга". У рамках цієї статті до вашої уваги пропонується практикум з вирішення завдань на тему “Машина Тьюринга”. Теоретичний матеріал з цієї теми неодноразово друкувався на сторінках газети “Інформатика”, наприклад, у № 3/2004 стаття І.М. Фаліна "Елементи теорії алгоритмів".

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

У кожній машині Тьюринга є дві частини:

1)необмеженав обидві сторони стрічка, Поділена на комірки;

2) автомат(Головка для зчитування/запису, керована програмою).

З кожною машиною Тьюринга пов'язані два кінцеві алфавіти: алфавіт вхідних символів A = (a 0, a 1, ..., a m) і алфавіт станів Q = (q 0, q 1, ..., q p). (З різними машинами Т'юрінга можуть бути пов'язані різні алфавіти Aі Q.) Стан q 0 називається пасивним. Вважається, що якщо машина потрапила в цей стан, вона закінчила свою роботу. Стан q 1 називається початковим. Перебуваючи у цьому стані, машина починає свою роботу.

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

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

Автомат щоразу "бачить" тільки один осередок. Залежно від того, яку букву aiвін бачить, а також залежно від свого стану qjавтомат може виконувати такі дії:

• · Записати нову літеру в оглядувану комірку;
• · Виконати зсув по стрічці на одну комірку вправо / вліво або залишитися нерухомим;
• · Перейти в новий стан.

Тобто машина Тьюринга має три види операцій. Щоразу для чергової пари ( q j, a i) машина Тьюринга виконує команду, що з трьох операцій із певними параметрами.

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

Клітина ( q j, a i) визначається двома параметрами - символом алфавіту та станом машини. Команда є вказівкою: куди пересунути головку читання/запису, який символ записати в поточну комірку, в який стан перейти машині. Для позначення напрямку руху автомата використовуємо одну з трьох літер: "Л" (ліворуч), "П" (вправо) або "Н" (нерухомий).

Після виконання автоматом чергової команди він переходить у стан q m(яке може в окремому випадку збігатися з колишнім станом q j). Наступну команду потрібно шукати у m-й рядку таблиці на перетині зі стовпцем a l(букву a lавтомат бачить після зсуву).

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

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

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

Рішення. Машина має додати одиницю до останньої цифри числа. Якщо остання цифра дорівнює 9, її замінити на 0 і додати одиницю до попередньої цифре. Програма для даної машини Тьюринга може виглядати так:

У цій машині Тьюринга q 1 - стан зміни цифри, q 0 - стан зупинки. Якщо може q lавтомат бачить цифру 0..8, він замінює її на 1..9 відповідно і перетворюється на стан q 0, тобто. машина зупиняється. Якщо ж він бачить цифру 9, то замінює її на 0, зрушується вліво, залишаючись у стані q l. Так триває до того часу, поки автомат не зустріне цифру менше 9. Якщо всі цифри дорівнювали 9, він замінить їх нулями, запише 0 дома старшої цифри, зрушить вліво й у порожній клітці запише 1. Потім перейде у стан q 0, тобто. зупиниться.

Практичні завдання

1. На стрічці машини Тьюринга міститься послідовність символів "+". Напишіть програму для машини Тьюринга, яка кожен другий символ "+" замінить на "-". Заміна починається з правого кінця послідовності. Автомат у стані q 1 оглядає один із символів зазначеної послідовності. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

2. Дано число nу восьмеричній системі числення. Розробити машину Тьюринга, яка збільшувала б задане число nна 1. Автомат у стані q 1 оглядає якусь цифру вхідного слова. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

3. Дано десятковий запис натурального числа n> 1. Розробити машину Тьюринга, яка б зменшувала задане число nна 1. Автомат у стані q 1 оглядає праву цифру числа. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

4. Дано натуральне число n> 1. Розробити машину Тьюринга, яка б зменшувала задане число nна 1, причому у вихідному слові старша цифра має бути 0. Наприклад, якщо вхідним словом було “100”, то вихідним словом має бути “99”, а чи не “099”. Автомат у стані q 1 оглядає праву цифру числа. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

5. Даний масив з дужок, що відкривають і закривають. Побудувати машину Тьюринга, яка видаляла пари взаємних дужок, тобто. розташованих підряд "()".

Наприклад, дано ") (() (()", треба отримати ") ... ((".

Автомат у стані q

6. Дано рядок з літер “ a” та “ b”. Розробити машину Тьюринга, яка перемістить усі літери “ a” у ліву, а літери “ b” - у правій частині рядка. Автомат у стані q 1 оглядає крайній лівий символ рядка. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

7. На стрічці машини Т'юрінга знаходиться число, записане в десятковій системі числення. Помножити це число на 2. Автомат може q 1 оглядає ліву крайню цифру числа. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

8. Дано два натуральні числа mі nпредставлені в унарній системі числення. Відповідні набори символів “|” розділені порожньою клітиною. Автомат у стані q 1 оглядає правий символ вхідної послідовності. Розробити машину Т'юрінга, яка на стрічці залишить суму чисел mі n. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

9. Дано два натуральні числа mі n, представлених в унарній системі числення. Відповідні набори символів “|” розділені порожньою клітиною. Автомат у стані q 1 оглядає правий символ вхідної послідовності. Розробити машину Тьюринга, яка на стрічці залишить різницю чисел mі n. Відомо що m> n. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

10. На стрічці машини Тьюринга знаходиться десяткове число. Визначити, чи це число ділиться на 5 без залишку. Якщо ділиться, то записати праворуч від числа слово "так", інакше - "ні". Автомат оглядає якусь цифру вхідного числа. Крім самої програми-таблиці, описати словами, що виконується машиною у кожному стані.

В стані q 1 машина шукає правий кінець числа, може q 2 - пропускає знак “+”, досягши кінця послідовності - зупиняється. В стані q 3 машина знак “+” замінює на знак “–”, при досягненні кінця послідовності вона зупиняється.

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

Стан q 1 - зменшуємо молодшу (чергову) цифру на 1. Якщо вона не дорівнює нулю, то після зменшення відразу - зупинка, якщо ж молодша цифра дорівнює 0, замість неї пишемо 9, зміщуємося вліво і знову виконуємо віднімання. До клітки [ a 0 , q 1] машина Тьюринга ніколи не потрапить, тому її можна не заповнювати.

Завдання 4 (ускладнення задачі 3)

Стан q 1 - зменшуємо молодшу (чергову) цифру на 1. Якщо вона більша за 1, то після зменшення - відразу зупини, якщо ж молодша цифра дорівнює 0, то замість неї пишемо 9, зміщуємося вліво і знову виконуємо віднімання. Якщо цифра, що зменшується, дорівнює 1, то замість неї пишемо 0 і переходимо в стан q 2 .

Стан q 2 - після запису “0” у якомусь розряді треба проаналізувати, чи не є цей нуль старшою цифрою (тобто не варто ліворуч від нього в записі вихідного слова). a 0).

Стан q 3 - якщо записаний "0" є старшою незначною цифрою, його треба видалити із запису вихідного слова.

Ті клітини, в які машина Тьюринга ніколи не потрапляє, залишаємо порожніми.

Стан q 1: якщо зустріли "(", то зрушення вправо і перехід у стан q 2; якщо зустріли “ a 0”, то зупин.

Стан q 2: аналіз символу "(" на парність, у разі парності повинні побачити ")". Якщо парна, то повернення вліво і перехід у стан q 3 .

Стан q 3: стираємо спочатку "(", потім ")" і переходимо в q 1 .

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

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

aaa ->

a -> вихідне слово збігається з вхідним, переглядаємо вхідне слово до того часу, поки воно закінчується.

bbb -> вихідне слово збігається з вхідним, переглядаємо вхідне слово до того часу, поки воно закінчується.

b -> вихідне слово збігається з вхідним, переглядаємо вхідне слово до того часу, поки воно закінчується.

ab -> вихідне слово збігається з вхідним, переглядаємо вхідне слово до того часу, поки воно закінчується.

Результат обговорення. Машина Тьюринга повинна “розуміти”, ланцюжком яких букв вона йде, тобто. у неї має бути як мінімум два стани. Нехай стан q 1 - рух по ланцюжку з літер “ a”, а q 2 - стан руху по ланцюжку з букв “ b”. Зауважимо, що ланцюжок може складатися і з однієї літери. Якщо ми дійшли до кінця рядка в стані q 1 або q 2, тобто. зустріли a 0 , машина повинна зупинитися, ми обробили весь рядок.

Розглянемо такі варіанти вхідних слів:

bba -> abb

bbbaab -> aabbbb

aabbbaab -> aaaabbbb

Результат обговорення. Перший варіант вхідного слова можна послідовно обробити так: bba -> bbb-> повернутися до лівого кінця ланцюжка з букв “ b” -> abb(замінити першу літеру в цьому ланцюжку на “ a”). Для виконання цих дій нам потрібно буде ввести два нових стани і, крім того, уточнити стан q 2 . Таким чином, для вирішення цього завдання нам потрібно побудувати машину Т'юрінга з такими станами:

q 1 - йдемо вправо по ланцюжку букв “ a”. Якщо ланцюжок закінчується a 0 , то переходимо в q 0; якщо закінчується буквою “ b”, то переходимо до q 2 ;

q 2 - йдемо вправо по ланцюжку букв “ b”, якщо ланцюжок закінчується a 0 , то переходимо в q 0; якщо закінчується “ a”, то замінюємо букву “ a” на “ b”, переходимо у стан q 3 (ланцюжок виду замінили на ланцюжок виду);

q 3 - йдемо вліво по ланцюжку букв “ b” до її лівого кінця. Якщо зустріли a 0 або “ a”, то переходимо до q 4 ;

q 4 - замінюємо “ b” на “ a” і переходимо у q 1 (ланцюжок виду замінюємо на ланцюжок виду .

Завдання 7

стан q 1 - пошук правої (молодшої) цифри числа;

стан q 2 -множення чергової цифри числа на 2 без додавання 1 перенесення;

стан q 3 - множення чергової цифри числа на 2 з додаванням 1 перенесення.

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

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

У цьому випадку їхня програма виглядає наступним чином:

стан q 1-пошук роздільника;

стан q 2 -пересунули штрих;

стан q 3 -перевірка на кінець (чи всі штрихи пересунули).

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

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

Ідея рішення (умова зупинки). На стрічці є два вихідні масиви штрихів.

Штрихи починаємо прати з лівого кінця масиву m. І по черзі стираємо найлівіший штрих у масиві mі найправіший штрих у масиві n. Але перш ніж стерти правий штрих у масиві n, перевіряємо, чи єдиний він (тобто останній, який треба стерти) чи ні.

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

Стан q 1 - пошук роздільника між масивами штрихів під час руху праворуч наліво;

стан q 2 - пошук лівого штриха в масиві m;

стан q 3 - видалення лівого штриха в масиві m;

стан q 4 - пошук роздільника під час руху зліва направо;

стан q 5 - пошук правого штриха в масиві n;

стан q 6 - перевірка єдиності цього штриха в масиві n, тобто. визначаємо, чи він останнім;

стан q 7 - якщо він був останнім, то зупинка, інакше перехід на новий цикл виконання алгоритму.

При вирішенні цього завдання слід звернути увагу на правильне виписування алфавіту:

A = ( a 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Д, А, Н, Е, Т).

Стан q 1-пошук правого кінця числа;

стан q 2-аналіз молодшої цифри числа; якщо вона дорівнює “0” чи “5”, тобто. число ділиться на 5, то перехід у стан q 3 , інакше перехід у стан q 5 ;

стан q 3-запис літери "Д" праворуч від слова на стрічці;

стан q 4 -запис літери "А" праворуч від слова та зупинки машини;

стан q 5 -запис літери "Н" праворуч від слова;

стан q 6 - запис літери "Е" праворуч від слова;

стан q 7 -запис літери "Т" праворуч від слова та зупинка машини.

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

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

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

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

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

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

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

ВІД РЕДАКЦІЇ

Усі наведені у статті завдання можна вирішити просто у зошиті, накресливши інформаційну стрічку та програму-таблицю. Але можна зробити цей процес цікавішим і наочнішим: скористатися машинною реалізацією - інтерпретатором машини Посту та машини Тьюринга “Algo2000”, створеним Радиком Зартдіновим. Програма має інтуїтивно зрозумілий інтерфейс, і вимоги у неї найпомірніші: комп'ютер IBM PC AT 486 і вище, наявність операційної системи Windows"95/98/NT.

Подивимося загалом, як працює “Algo2000”.

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

Перед нами з'явиться поле машини Тюрінга.

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

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

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

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

Поле програми виглядатиме так:

Формат команди у кожному осередку - aKq. Тут:
a - новий зміст поточного осередку (новий символ зовнішнього алфавіту, який заноситься в поточний осередок), K - команда стрічкопротяжного механізму машини Тьюринга (вліво, вправо, стоп), q - новий внутрішній стан машини Тьюринга.

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

Програму можна виконати кроками. Для цього натисніть кнопку на панелі інструментів (якщо кнопки не видно, потрібно вибрати пункт меню Вид | Панель інструментів) або виберіть у головному меню Пуск | Покроково. Якщо необхідно повністю перервати виконання програми, це можна зробити за допомогою кнопки на панелі інструментів або за допомогою головного меню ( Пуск | Перервати). Пункт меню Швидкістьдозволяє регулювати швидкість виконання програми.

Виконання програми буде йти доти, доки не зустрінеться команда “Стоп” або не виникне якась помилка.

У разі виникнення питань під час роботи з програмою-інтерпретатором звертайтеся до довідкового файлу Algo2000.hlp. Його, як і саму програму “Algo2000”, можна знайти на сайті газети “Інформатика” http://inf.1september.ruу розділі "Download".

Штучний інтелект (ІІ, англ. Artificial intelligence, AI) – наука та технологія створення інтелектуальних машин, особливо інтелектуальних комп'ютерних програм. ІІ пов'язані з подібним завданням використання комп'ютерів розуміння людського інтелекту, але з обов'язково обмежується біологічно правдоподібними методами.

Що таке штучний інтелект

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

На початку 1980-х років. вчені в галузі теорії обчислень Барр та Файгенбаум запропонували наступне визначення штучного інтелекту (ІІ):

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

Основні властивості ІІ - це розуміння мови, навчання та здатність мислити і, що важливо, діяти.

ІІ – комплекс споріднених технологій і процесів, що розвиваються якісно та стрімко, наприклад:

• обробка тексту природною мовою
• експертні системи
• віртуальні агенти (чат-боти та віртуальні помічники)
• системи рекомендацій.

Національна стратегія розвитку штучного інтелекту

• Основна стаття:Національна стратегія розвитку штучного інтелекту

Дослідження у сфері ІІ

• Основна стаття:Дослідження у сфері штучного інтелекту

Стандартизація в галузі ІІ

2019: Експерти ISO/IEC підтримали пропозицію щодо розробки стандарту російською мовою

16 квітня 2019 року стало відомо, що підкомітет ISO/IEC зі стандартизації в галузі штучного інтелекту підтримав пропозицію Технічного комітету «Кібер-фізичні системи», створеного на базі РВК, щодо розробки стандарту «Artificial intelligence. Concepts and terminology» російською мовою на додаток до базової англійської версії.

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

За підсумками засідання профільного підкомітету ISO/IEC у Дубліні експерти ISO/IEC підтримали пропозицію делегації з Росії щодо синхронної розробки термінологічного стандарту у сфері AI не лише англійською, а й російською мовою. Очікується, що документ буде затверджено на початку 2021 року.

У ході засідання експерти ISO/IEC також підтримали розробку проекту міжнародного документа Information Technology - Artificial Intelligence (AI) - Overview of Computational Approaches for AI Systems, у якому Росія виступає як співредактор. Документ надає огляд сучасного стану систем штучного інтелекту, описуючи основні характеристики систем, алгоритми та підходи, а також приклади спеціалізованих додатків у галузі AI. Розробкою цього проекту документа займеться спеціально створена в рамках підкомітету робоча група 5 "Обчислювальні підходи та обчислювальні характеристики систем штучного інтелекту" (SC 42 Working Group 5 "Computational approaches and computational characteristics of AI systems").

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

У напрямку штучного інтелекту ТК «Кібер-фізичні системи» на базі РВК веде розробку низки національних стандартів, затвердження яких заплановано на кінець 2019 – початок 2020 року. Крім того, спільно з ринковими гравцями йде робота щодо формування Плану національної стандартизації (ПНР) на 2020 рік і далі. ТК «Кібер-фізичні системи» відкрито для пропозицій щодо розробки документів із боку зацікавлених організацій.

2018: Розробка стандартів у галузі квантових комунікацій, ІІ та розумного міста

Технічний комітет «Кібер-фізичні системи» на базі РВК спільно з Регіональним інжиніринговим центром «СейфНет» 6 грудня 2018 року розпочали розробку комплексу стандартів для ринків Національної технологічної ініціативи (НТІ) та цифрової економіки. До березня 2019 року планується розробити документи технічної стандартизації в галузі квантових комунікацій, та повідомили в РВК. Детальніше .

Вплив штучного інтелекту

Ризик у розвиток людської цивілізації

Вплив на економіку та бізнес

• Вплив технологій штучного інтелекту на економіку та бізнес

Вплив ринку праці

Упередженість штучного інтелекту

В основі всього того, що є практикою ІІ (машинний переклад, розпізнавання мови, обробка текстів природними мовами, комп'ютерний зір, автоматизація водіння автомобілів та багато іншого) лежить глибинне навчання. Це підмножина машинного навчання, яке відрізняється використанням моделей нейронних мереж, про які можна сказати, що вони імітують роботу мозку, тому їх з натяжкою можна віднести до ІІ. Будь-яка модель нейронної мережі навчається на великих наборах даних, таким чином, вона набуває деяких «навичок», але те, як вона ними користується - для творців залишається не ясним, що в кінцевому рахунку стає однією з найважливіших проблем для багатьох програм глибинного навчання. Причина в тому, що така модель працює з образами формально, без розуміння того, що вона робить. Чи є така система ІІ і чи можна довіряти системам, побудованим з урахуванням машинного навчання? Значення відповіді останнє питання виходить межі наукових лабораторій. Тому помітно загострилася увага засобів масової інформації до явища, яке отримало назву AI bias. Його можна перекласти як «необ'єктивність ІІ» або «упередженість ІІ». Детальніше .

Ринок технологій штучного інтелекту

Ринок ІІ в Росії

Світовий ринок ІІ

Сфери застосування ІІ

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

ІІ - це монолітна предметна область. Більше того, деякі технологічні напрямки ІІ фігурують як нові підгалузі економіки та відокремлені сутності, одночасно обслуговуючи більшість сфер економіки.

Розвиток застосування використання ІІ веде до адаптації технологій у класичних галузях економіки по всьому ланцюжку створення цінності та перетворює їх, призводячи до алгоритмізації практично всього функціоналу, від логістики до управління компанією.

Використання ІІ з метою оборони та у військовій справі

Використання в освіті

Використання ІІ у бізнесі

ІІ у боротьбі з шахрайством

11 липня 2019 стало відомо про те, що всього через два роки штучний інтелект і машинне навчання будуть використовуватися для протидії шахрайству втричі частіше, ніж на липень 2019 року. Такі дані були отримані під час спільного дослідження компанії SAS та Асоціації сертифікованих фахівців із розслідування розкрадань та шахрайства (Association of Certified Fraud Examiners, ACFE). На липень 2019 року такі антифрод-інструменти вже використовують у 13% організацій, які взяли участь в опитуванні, і ще 25% заявили, що планують їх впровадити протягом найближчого року-двох. Детальніше .

ІІ в електроенергетики

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

ІІ у виробничій сфері

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

ІІ в банках

• Розпізнавання образів – використовується у т.ч. для впізнавання клієнтів у відділеннях та передачі їм спеціалізованих пропозицій.

ІІ на транспорті

• Автоіндустрія на порозі революції: 5 викликів епохи безпілотного водіння

ІІ в логістиці

ІІ у пивоварінні

ІІ у судовій системі

Розробки в галузі штучного інтелекту допоможуть кардинально змінити судову систему, зробити її більш справедливою та вільною від корупційних схем. Таку думку висловив влітку 2017 доктор технічних наук, технічний консультант Artezio Володимир Крилов.

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

«Щодня переглядаючи новинні повідомлення про розробки в галузі ІІ тільки дивуєшся невичерпності фантазії та плідності дослідників та розробників у цій галузі. Повідомлення про наукові дослідження постійно чергуються з публікаціями про нові продукти, що вриваються на ринок та повідомленнями про дивовижні результати, отримані за допомогою застосування ІІ в різних галузях. Якщо ж говорити про очікувані події, які супроводжуються помітним хайпом у ЗМІ, в якому ІІ стане знову героєм новин, то я, напевно, не ризикну робити технологічних прогнозів. Можу припустити, що найближчою подією стане поява десь гранично компетентного суду у формі штучного інтелекту, справедливого та непідкупного. Станеться це, мабуть, у 2020-2025 роках. І процеси, які пройдуть у цьому суді, призведуть до несподіваних рефлексій та прагнення багатьох людей передати ІІ більшість процесів управління людським суспільством».

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

Музика

Живопис

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

26 лютого 2016 року в Сан-Франциско на спеціальному аукціоні представники Google виручили із психоделічних картин, написаних штучним інтелектом, близько $98 тис. Ці кошти були пожертвовані на благодійність. Одна з найвдаліших картин машини представлена ​​нижче.

Картина написана штучним інтелектом Google.

We see it all the time. "RESTful" this, "REST" protocol that, etc. However, lot of us don't дійсно understand exactly what it means. We’ll fix exactly that gap in this article!

State

У комп'ютерних науках (і математичних, до деяких extent), є поняттям держави. A certain system can be in state A or it can be in state B or it can be a bunch of others states (usually, a finite list of states).

Як нагадує, що ви думаєте, що ви збираєтеся програмою, які знімають ручку, якщо температура є більше ніж 80 градусів farenheit, або turns it blue, і якщо ця температура є незважаючи на 80 градусів farenheit.

We can call the first state (temp > 80 degrees) state “A” and the second state (temp< 80 degrees) state “B”. We’ll call the middling state (temp = 80 degrees) state “C”. As we can see, we have defined behaviours of the programs at state A and state B, but not at state C.

Це є головна ідея штату. Here’s the definition given by the all-knowing Wikipedia:

“У комп'ютерній академії і автоматизації теорії, державний логічний circuit або комп'ютерний програма є технічною термою для всіх повідомлень, введених в точці часу, які є використані для circuit or program.”

У шорті, це є sort of “з'єднання” всіх повідомлень, що програма проходить в акаунті.

Тепер, ми йти до макіяжу, щоб потрапити в деякий час, що вважається великим теоретичним і корисним і деяким з'єднанням до дуже практичний світ REST.

Turing machines

Там був цей чоловік званий Alan Turing, і він був quite a smart mathematician with interest in workings of computers. Він вважає, що imaginary computer (який, як ми будемо бачити, є фактично неможливим до сучасного будівництва), який був використаний для того, щоб думати про те, що з'являються в реальних комп'ютерах.

Комп'ютер складається з tape of infinite length, with head through which the tape passes. На tape є “cells”, до яких інформація може бути написана (номери, кольори, etc.) The tape moves через цей машина, лівий або правий, один пристрій на час. Машини сканування в whatever є already on tape and, depending on what state it is in, it writes something back on the tape then, subsequently, changes its state.

Ви можете скористатися тим, що definition again for it to sink in completely. Принцип ідеї є те, що він виконує операції на пам'яті, що базуються на державних і державних змінах в залежності від операцій на пам'яті.

Це тому, що досить невблаганна теоретична фантазія (начебто, є абсолютно не погано, що, read A Mathematician's Apology if you're wondering why people care to take an interest in theoretical stuff). However, it is quite possibly the most fundamental concept of computer science.

Використовуючи Turing Machine, комп'ютерні школярі можуть бути здатні до будь-якої algoritm, що може бути виконана на комп'ютері. У fact, Turing machine має led to many advances in computer science.

So, The Turing Machine shows us that today (note: I'm не розглядає graph reduction processors), literally everything in computer science is based off the idea of ​​state.

The Network

Там буде вестися до концепції Інтернету. Це є місце, де пакети можуть проходити wire і є незмінним для них їхній destination. У загальних випадках, є невідповідно до повної трансмісії повного часу.

Clients come in quickly and leave twice as fast. Як таке, тримаючись за допомогою клієнта штату, не можна робити, коли працює на мережній системі.

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

Нові, люди потребують мережі протоколу для Інтернету, який був простим, швидким і розширеним управлінням штату добре в сучасному динамічному середовищі.

Що protocol був HTTP, і theory те, що grew out of work on HTTP був labelled REST.

REST

REST stands for: REpresentational State Transfer. Це система системи, що розташована в межах “client-server”, що те, що мережа є побудована на верхній частині (добре, там є peer на peer типу мережі, але, клієнт-сервер є вірно, що простий і найбільш tested architecture). Назву йогоselfl є вельми незважаючи на те, що сервер є повністюдержавним!

Там є кілька побоїв, що всі системи, що claim to be “RESTful” must follow.

First of all, it must be a client-server system. Цей бік має бути змінений в pas, але в formal definition (і для теорії REST до роботи properly), ми маємо сервери для яких клієнтів може бути підключений.

The server is fully stateless. Це означає, що для кожного клієнта необхідно до сервера, а не держава буде відправлена ​​на сервер. Для прикладу, якщо клієнт (за допомогою HTTP), запити на index сторінку і наступні запити на /user/home page, на двох реакціях є повністю незалежно від всіх інших. The client holds all of the state of the system (hence, we have the back button).

Responses from the server must be cacheable, which means that there must be as system on the server which identifies respones as cacheable or not, so that clients (e.g. web browsers) може взяти звідти cache.

Нарешті, ми повинні мати простий, clean, і uniform interface. Якщо ви маєте деякий досвід з тим, як HTTP робіт, потрібні форми є дуже простими. Вони є великими verbs and nouns with as easy to parse and human-readable format. SOAP є іншою формою мережі протоколу, який пов'язаний з цим вимогою і,поки що, є дуже difficult до роботи з.

Now, what do all of these properties, when taking together, entail?

Implications of REST

They let us build systems that are cleanly seperated, scalable, and debugged easily.

Let us consider the restriction of statelessness on the server first, it may well be the most important (and, also, the most often violated by so-called RESTful architectures) bit.

Як попередньо mentioned, в клієнт-сервер архітектури клієнтів є дуже німблі; вони мають перші запити і suddenly kill all communication. У цьому малюнку зайнятості, це дуже чутливий до себе, не може залишатися державою про клієнта на сервері. Ці lets us reason about HTTP servers very easily; Всі клієнти, які можуть бути вирішені, якщо це повністю новий клієнт, і це буде робити, як penny of a difference.

Secondly, cacheable response mean that the clients are able to get data much faster, because often times, the data can be retrieved from the client's memory. Це неодмінно збільшує поточний розвиток і, в деяких системах, сервер стійкості.

The uniform interface може just be the most important. Маючи працювали з SOAP, я може казати, що HTTP's простий формат є blessing, коли trying до debug server code і ті ж самі applies до інших RESTful systems.

Designing a RESTful System

Let’s say we need to write a server that returns stock quotes, as well as retaining list of stock quotes to monitor (and, the user can either add to or clear the list).

Це є простим чином для RESTful system, тому що він є врівноважені незалежності від identity of client. Там,поки сервер не потрібний не будь-який час про клієнта.

We first start by defining how the protocol language will work (а bit like the GET and POST verbs of HTTP):

GETQUOTE ticker- gives the price for a particular stock
ADDTICKER ticker- adds given stock to the list
GETLIST - gets a comma separated list of stocks in the list

Це fairly simple protocol, and, doesn't продовжує бути на сайті. Тепер, як для покупки, ми можемо думати, що будуть update prices every hour, so caches more t one hour old may be thrown away.

And, that's all there is to it! З курсу, ми повинні реалізувати це, але, загальна думка системи є quite simple and clean!

Conclusion

Hopefully, цей article gave you a solid understanding of REST.

Also, I hope that you will now be able to call out people who throw around the term “RESTful” too much - I can tell you, there's a lot of them!

ТЬЮРІНГ

ТЬЮРІНГ(Turing) Алан (1912-54), англійський математик і логік, який сформулював теорії, що згодом стали основою комп'ютерної техніки. У 1937 р. вигадав машину Тьюринга -гіпотетичну машину, здатну перетворювати набір команд, що вводяться. Вона була провісницею сучасних комп'ютерів. Тьюрінг також використав ідею комп'ютера, щоб дати альтернативний і простіший доказ теореми ГЕДЕЛЯ про неповноту. Тьюрінг зіграв основну роль розгадці «Енігми» (Enigma) - комплексного методу шифрування, який використовувала Німеччина під час Другої світової війни. У 1948 р. брав участь у створенні одного з перших у світі комп'ютерів. У 1950 р. вигадав тест Тьюринга -передбачалося, що це тест здатність комп'ютера «мислити». По суті, в ньому стверджувалося, що людина не зможе відрізнити діалог з машиною від діалогу з іншою людиною. Ця робота проклала шлях до створення ШТУЧНОГО ІНТЕЛЕКТУ. Т'юрінг також займався теоретичною біологією. В роботі "Хімічна основа морфогенезу"(1952) він запропонував модель, що описує походження різних схем будови організмів у біології. З того часу такі моделі часто застосовуються для опису та пояснення багатьох систем, що спостерігаються в природі. Т'юрінг наклав на себе руки, будучи офіційно звинувачений у гомосексуалізмі.

Науково-технічний енциклопедичний словник.

Дивитись що таке "ТЮРІНГ" в інших словниках:

Т'юрінг, Алан Матісон Алан Т'юрінг Alan Mathison Turing Пам'ятник у Секвіль Парку Дата народження … Вікіпедія

- (Turing) Алан Матісон (1912-54), англійський математик. У 1936-1937 ввів математичне поняття абстрактного еквівалента алгоритму, або обчислюваної функції, що отримала потім назву машина Тьюринга. Сучасна енциклопедія

- (Turing), Алан Матісон (23 червня 1912 - 7 червня 1954) - англ. логік та математик. У 1936–37 запропонував ідеалізовану машинну модель обчислити. процесу - обчислювальну схему, близьку до дій людини, що робить обчислення, і висунув ... Філософська енциклопедія

Т'юрінг А.– Т'юрінг А. Англійський математик. Тема захисту інформації EN Turing … Довідник технічного перекладача

Алан Т'юрінг Alan Turing Пам'ятник у Секвіль Парку Дата народження: 23 червня 1912 Місце народження: Лондон, Англія Дата смерті: 7 червня 1954 … Вікіпедія

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

- (Turing) Алан Матісон (23.6.1912, Лондон, 7.6.1954, Вілмслоу, поблизу Манчестера), англійський математик. Член Королівського товариства (1951). Після закінчення Кембриджського університету (1935) працював над докторською дисертацією в Прінстонському. Велика Радянська Енциклопедія

Т'юрінг А. М.- ТЬЮРИНГ (Turing) Алан Матісон (1912 54), англ. математик. основ. тр. з матем. логікою, обчислить. математики. У 1936?37 ввів матем. поняття абстрактного еквівалента алгоритму, або обчислюваної функції, яке отримало потім назв. машина Т … Біографічний словник

- (Повн. Алан Матісон Тьюрінг, Alan Mathison Turing) (23 червня 1912, Лондон 7 червня 1954, Вілмслоу, Великобританія), британський математик, автор праць з математичної логіки, обчислювальної математики. У 1936-1937 роках ввів математичне поняття. Енциклопедичний словник

Книги

• Чи може машина думати? Загальна та логічна теорія автоматів. Випуск 14, Тьюрінг А., Справжня книга, що містить роботи Алана Тьюринга і Джона фон Неймана, що стояли біля витоків створення перших мислячих машин ЕОМ, відноситься до класики філософсько-кібернетичного ... Категорія: Бази даних Серія: Науки про штучне Видавець: URSS, Виробник: URSS,
• Чи може машина думати? Загальна та логічна теорія автоматів. Випуск № 14 , Тьюрінг А. , Справжня книга, що містить роботи Алана Тьюринга і Джона фон Неймана, що стояли біля витоків створення перших «мислячих машин» ЕОМ, відноситься до класики філософсько-кібернетичного напряму.