Відмінності між версіями «Обчислюваність»

Доповнено розділ.
(Доповнено розділ.)
; {{Не перекладено|P′′|P′′|en|P′′}}
: Як і машини Тьюрінга, P′′ використовує нескінченну стрічку символів (без довільного доступу) і досить мінімалістичний набір інструкцій. Але ці інструкції дуже різні, таким чином, на відміну від машин Тьюрінга, P′′не потрібно підтримувати окремий стан, тому що вся функціональність, пзалежнапвід ам'яті, може бути забезпечена тоднієюслиш трічкою. Замість того, щоб переписувати поточний символ, вона може виконати для нього опреацію [[Модульна арифметика|модульної суми]] з одиницею. P′′ має також пару інструкцій циклів, та для перевірки на порожній символ. Незважаючи на свій мінімалістичний характер, ця машина стала батьківською формальною мовою для мови програмування під назвою [[Brainfuck]].
 
На додаток до загально відомих обчислювальних моделей, існують деякі більш прості обчислювальні моделі, які корисні для специфічних, обмежених застосувань. [[Регулярний вираз|Регулярні вирази]], наприклад, визначають шаблони рядків у багатьох контекстах, від програмного забезпечення для офісної роботи до [[Мова програмування|мов програмування]]. Інша формальна математично еквівалентна регулярним виразам структура, [[Скінченний автомат|скінченні автомати]], використовується в [[Схемотехніка|схемотехніці]] і в деяких рішеннях задач. [[Контекстно-вільна граматика|Контекстно-вільні граматики]] задають синтаксис мов програмування. Недетермінований автомат з [[Автомат з магазинною пам'яттю|магазинною пам'яттю]] — ще одна формальна структура, еквівалентна контекстно-вільним граматикам.
 
Різні моделі обчислень мають різні можливості виконувати різні завдання. Одним із способів вимірювання потужності обчислювальної моделі є вивчення класу формальних мов, які може генерувати модель; таким чином отримується [[Ієрархія Чомскі|ієрархія мов Чомскі]].
 
Інші обмежені моделі обчислення включають:
 
;[[Детермінований скінченний автомат|Детермінований скінчений автомат]]:На сьогоднішній усі реальні обчислювальні пристрої можна змоделювати як машини зі скінченою кількістю станів, оскільки всі реальні комп'ютери працюють на скінчених ресурсах. Така машина має набір станів і набір переходів, на які впливає потік вхідних даних. Деякі стани визначені кінцевими. Вхідний потік подається в машину одним символом за раз, переходи між станами порівнюються з вхідним символом, і якщо є відповідний перехід, машина переходить в новий стан. Якщо в кінці вхідного потоку машина знаходиться в кінцевому стані, то увесь вхідний потік є таким, що приймається даною машиною.
;[[Недетермінований скінченний автомат|Недетермінований скінчений автомат]]:Інша проста модель обчислення, хоча послідовність її виконання не визначена однозначно. Вона може бути інтерпретована як одночасне виконання декількох варіантів обчислення з використанням кінцевого числа станів. Однак можна довести, що будь-який недетермінований автомат зводиться до еквівалентного йому детермінованого.
;[[Автомат з магазинною пам'яттю]]:Подібний до кінцевого автомата, за винятком того, що він має [[стек]], якому дозволено зростати до довільного розміру. Переходи станів додатково вказують, чи слід додавати символ до стека або вилучати символ зі стека. Ця модель є більш потужною, ніж кінцевий автомат завдяки своєму нескінченному стеку (пам'яті), хоча тільки верхній елемент стека доступний в окремий момент часу.
 
== Див. також ==
55

редагувань