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

м
Шаблони нп, виправив помилки.
(доповнення)
м (Шаблони нп, виправив помилки.)
'''Обчислюваність''' — це властивість задачі бути ефективно розв'язаною. Це ключова тема в області [[Теорія обчислюваності|теорії обчислюваності]] в рамках [[Математична логіка|математичної логіки]] і [[Теорія алгоритмів|теорії алгоритмів]] у [[Інформатика|інформатиці]]. Обчислюваність задачі тісно пов'язана з задачею існування [[Алгоритм|алгоритму]] для її вирішення.
 
Найбільш широко вивченими моделями обчислюваності є [[Машина Тюрінга|ТьюрінгТюрінг-обчислювальні]] і {{Нп|μ-рекурсивна функція|μ-рекурсивні функції|en|μ-recursive function}}, та [[лямбда-числення]], всі з них мають парно еквівалентну обчислювальну потужність (алгоритми побудовані для однієї системи мають відповідники у інших). Досліджуються й інші форми обчислюваності: в [[Теорія автоматів|теорії автоматів]] вивчаються поняття обчислюваності, які слабкіші за машини ТьюрингаТюринга, тоді як області [[Гіперобчислення|гіперобчислень]] вивчаються сильніші поняття обчислюваності.
 
== Задачі ==
 
== Формальні моделі обчислень ==
[[Модель обчислення]] — це формальний опис особливого типу обчислювального процесу. Такий опис часто має форму [[Автомат (дискретна математика)|абстрактної машини]], яка призначена для виконання поставленого завдання. До загально відомих моделей обчислення, еквівалентним [[Машина Тюрінга|машині ТьюрингаТюринга]] (див. [[Теза Черча — Тюрінга|тезу Черча-ТьюрінгаТюрінга]]), належать:
 
; [[Лямбда-числення]]: Обчислення складається з початкового лямбда-виразу (або двох, якщо ви хочете відокремити функцію та його вхідні дані) та кінцева послідовність лямбда термів, кожен з яких виведено з попереднього терму застосуванням [[Лямбда-числення|бета-редукції]].
; {{Не перекладено|Система перезапису рядків|Системи перезапису рядків|en|Semi-Thue system}}
: Включають [[Нормальні алгоритми|алгоритми Маркова]], які використовують правила схожі на правила [[Граматика|граматик]] для роботи над [[Рядок (програмування)|рядками]] символів; також [[числення Поста]].
; [[Машина з натуральнозначними регістрами|Регістрова машина]]: Теоретично цікава ідеалізація комп'ютера. Існує декілька її варіантів. У більшості з них кожен реєстр може містити натуральне число необмеженого розміру, а інструкції прості і малочисельні, наприклад, машина, де існують тільки зменшення на одиницю (у поєднанні з умовним стрибком), збільшення на одиницю і зупинка машини. Відсутність нескінченної (або динамічно зростаючої) множини регістрів (яку можна побачити на машинах ТьюрингаТюринга) можна зрозуміти, замінивши її роль технікою [[Нумерація Геделя|нумерації Геделя]]: той факт, що кожен реєстр має натуральне число, дає можливість представити складну річ (наприклад послідовність або матрицю) за допомогою відповідного величезного натурального числа — однозначність як представлення, так і інтерпретації встановлюються [[Теорія чисел|числовою теорією]] основ цих методів.
; [[Машина Тюрінга|Машина ТьюрингаТюринга]]: Схожа на кінцевий автомат, за винятком того, що вхід подається на стрічці, яку машина ТьюрингаТюринга може читати, перезаписувати і по якій може вільно '''послідовно''' переміщатися (тобто не може перескакувати комірки стрічки). Стрічці дозволено зростати до довільного розміру. Машина ТьюрингаТюринга здатна виконувати складні обчислення, які можуть мати довільну тривалість. Ця модель є, мабуть, найважливішою моделлю обчислень у комп'ютерній науці, оскільки вона імітує обчислення за відсутності визначених обмежень ресурсів.
; {{Не перекладено|Багатострічкова машина Тюрінга|Машина Тьюринга з декількома стрічками|en|Multitape Turing machine}}
: Машина може мати більше однієї стрічки; крім того, може бути кілька головок на одну стрічку. Несподівано, будь-яке обчислення, яке може бути виконане цим родом машини, також може бути виконане звичайною машиною ТьюрінгаТюрінга, хоча остання може бути повільнішою або вимагати більше місця для стрічки.
; {{Не перекладено|P′′|P′′|en|P′′}}
: Як і машини ТьюрінгаТюрінга, P′′ використовує нескінченну стрічку символів (без довільного доступу) і досить мінімалістичний набір інструкцій. Але ці інструкції дуже різні, таким чином, на відміну від машин ТьюрінгаТюрінга, P′′ не потрібно підтримувати окремий стан, тому що вся функціональність, залежна від пам'яті, може бути забезпечена однією стрічкою. Замість того, щоб переписувати поточний символ, вона може виконати для нього операцію [[Модульна арифметика|модульної суми]] з одиницею. P′′ має також пару інструкцій циклів, та для перевірки на порожній символ. Незважаючи на свій мінімалістичний характер, ця машина стала батьківською формальною мовою для мови програмування під назвою [[Brainfuck]].
 
На додаток до загально відомих обчислювальних моделей, існують деякі більш прості обчислювальні моделі, які корисні для специфічних, обмежених застосувань. [[Регулярний вираз|Регулярні вирази]], наприклад, визначають шаблони рядків у багатьох контекстах, від програмного забезпечення для офісної роботи до [[Мова програмування|мов програмування]]. Інша формальна математично еквівалентна регулярним виразам структура, [[Скінченний автомат|скінченні автомати]], використовується в [[Схемотехніка|схемотехніці]] і в деяких рішеннях задач. [[Контекстно-вільна граматика|Контекстно-вільні граматики]] задають синтаксис мов програмування. Недетермінований автомат з [[Автомат з магазинною пам'яттю|магазинною пам'яттю]] — ще одна формальна структура, еквівалентна контекстно-вільним граматикам.
* [[Теорія автоматів]]
* [[Автомат (дискретна математика)|Автомат]]
*{{Не [[List of undecidable problemsперекладено|Список невирішених проблем обчислюваності]]||en|List of undecidable problems}}
* [[Теорія складності обчислень]]
*{{Не [[Computability logicперекладено|Логіка обчислюваності]]||en|Computability logic}}
 
== Джерела ==
55

редагувань