Обчислюваність — властивість задачі бути ефективно розв'язаною. Це ключова тема в області теорії обчислюваності в рамках математичної логіки і теорії алгоритмів у інформатиці. Обчислюваність задачі тісно пов'язана з задачею існування алгоритму для її вирішення.
Найбільш широко вивченими моделями обчислюваності є Тюрінг-обчислювальні і μ-рекурсивні функції, та лямбда-числення, всі з них мають парно еквівалентну обчислювальну потужність (алгоритми побудовані для однієї системи мають відповідники у інших). Досліджуються й інші форми обчислюваності: в теорії автоматів вивчаються поняття обчислюваності, які слабкіші за машини Тюрінга, тоді як області гіперобчислень вивчаються сильніші поняття обчислюваності.
Задачі
Центральною ідеєю теорії є [en], яка є практичним завданням, чию обчислюваність можна вивчати.
Існує два ключових типи проблем:
- Проблема вибору фіксує набір S, яким може бути набір рядків, натуральних чисел чи інших об'єктів, взятих з деякого більшого набору U. Проблема полягає у тому, чи заданий елемент u з U належить S. Наприклад, U — множина натуральних чисел і S множина простих чисел, відповідній задачі вибору відповідає тест на простоту.
- Функціональна проблема складається з функції f, у якою U є множиною визначення, а V — множиною значень. Дана проблема обчислює для даного елемента u з U відповідний елемент f(u) з V. Наприклад, U і V можуть бути множиною всіх скінчених двійкових рядків, тоді як f може приймати рядок і повертати рядок у зворотньому порядку (наприклад, f(0101) = 1010).
Інші типи проблем включають в себе задачу пошуку та задачу оптимізації.
Одна з цілей теорії обчислюваності полягає у визначенні, які проблеми або класи проблем можна вирішити в кожній з моделей обчислення.
Формальні моделі обчислень
Модель обчислення — це формальний опис особливого типу обчислювального процесу. Такий опис часто має форму абстрактної машини, яка призначена для виконання поставленого завдання. До загально відомих моделей обчислення, еквівалентним машині Тюринга (див. тезу Черча-Тюрінга), належать:
- Лямбда-числення
- Обчислення складається з початкового лямбда-виразу (або двох, якщо ви хочете відокремити функцію та його вхідні дані) та кінцева послідовність лямбда термів, кожен з яких виведено з попереднього терму застосуванням бета-редукції.
- Комбінаторна логіка
- Концепція, що має багато спільного з лямбда-численням, але яка має важливі відмінності (наприклад, комбінатор фіксованої точки Y має нормальну форму в комбінаторній логіці, але не в лямбда-численні). Комбінаторна логіка розвивалася маючи великі амбіції: отримати розуміння природи парадоксів, зробити основи математики більш економними (концептуально), усунути поняття змінної (таким чином, уточнивши її роль в математиці).
- μ-рекурсивні функції
- Обчислення складається з μ-рекурсивної функції, точніше, з послідовності, яка її визначає, будь-якого вхідного значення і послідовності рекурсивних функцій, що з'являються у визначеній послідовності з входами і виходами. Таким чином, якщо в визначальній послідовності рекурсивної функції f(x) з'являються функції g(x) і h(x,y), то можуть з'явитися терми виду g(5) = 7 або h(3,2) = 10. Кожен запис у цій послідовності повинен бути застосуванням базової функції або бути наслідком з вищезазначених записів, використовуючи композицію, примітивну рекурсію або μ-рекурсію. Наприклад, якщо f(x) = h(x,g(x)), то для появи f(5) = 3, терми g(5) = 6 і h(3,6) = 3 повинні з'явитися вище у послідовності. Обчислення припиняється тільки в тому випадку, якщо останній терм видає значення рекурсивної функції.
- [en]
- Включають алгоритми Маркова, які використовують правила схожі на правила граматик для роботи над рядками символів; також числення Поста.
- Регістрова машина
- Теоретично цікава ідеалізація комп'ютера. Існує декілька її варіантів. У більшості з них кожен реєстр може містити натуральне число необмеженого розміру, а інструкції прості і малочисельні, наприклад, машина, де існують тільки зменшення на одиницю (у поєднанні з умовним стрибком), збільшення на одиницю і зупинка машини. Відсутність нескінченної (або динамічно зростаючої) множини регістрів (яку можна побачити на машинах Тюринга) можна зрозуміти, замінивши її роль технікою нумерації Геделя: той факт, що кожен реєстр має натуральне число, дає можливість представити складну річ (наприклад послідовність або матрицю) за допомогою відповідного величезного натурального числа — однозначність як представлення, так і інтерпретації встановлюються числовою теорією основ цих методів.
- Машина Тюринга
- Схожа на кінцевий автомат, за винятком того, що вхід подається на стрічці, яку машина Тюринга може читати, перезаписувати і по якій може вільно послідовно переміщатися (тобто не може перескакувати комірки стрічки). Стрічці дозволено зростати до довільного розміру. Машина Тюринга здатна виконувати складні обчислення, які можуть мати довільну тривалість. Ця модель є, мабуть, найважливішою моделлю обчислень у комп'ютерній науці, оскільки вона імітує обчислення за відсутності визначених обмежень ресурсів.
- [en]
- Машина може мати більше однієї стрічки; крім того, може бути кілька головок на одну стрічку. Несподівано, будь-яке обчислення, яке може бути виконане цим родом машини, також може бути виконане звичайною машиною Тюрінга, хоча остання може бути повільнішою або вимагати більше місця для стрічки.
- P′′
- Як і машини Тюрінга, P′′ використовує нескінченну стрічку символів (без довільного доступу) і досить мінімалістичний набір інструкцій. Але ці інструкції дуже різні, таким чином, на відміну від машин Тюрінга, P′′ не потрібно підтримувати окремий стан, тому що вся функціональність, залежна від пам'яті, може бути забезпечена однією стрічкою. Замість того, щоб переписувати поточний символ, вона може виконати для нього операцію модульної суми з одиницею. P′′ має також пару інструкцій циклів, та для перевірки на порожній символ. Незважаючи на свій мінімалістичний характер, ця машина стала батьківською формальною мовою для мови програмування під назвою Brainfuck.
На додаток до загально відомих обчислювальних моделей, існують деякі більш прості обчислювальні моделі, які корисні для специфічних, обмежених застосувань. Регулярні вирази, наприклад, визначають шаблони рядків у багатьох контекстах, від програмного забезпечення для офісної роботи до мов програмування. Інша формальна математично еквівалентна регулярним виразам структура, скінченні автомати, використовується в схемотехніці і в деяких рішеннях задач. Контекстно-вільні граматики задають синтаксис мов програмування. Недетермінований автомат з магазинною пам'яттю — ще одна формальна структура, еквівалентна контекстно-вільним граматикам.
Різні моделі обчислень мають різні можливості виконувати різні завдання. Одним із способів вимірювання потужності обчислювальної моделі є вивчення класу формальних мов, які може генерувати модель; таким чином отримується ієрархія мов Чомскі.
Інші обмежені моделі обчислення включають:
- Детермінований скінчений автомат
- На сьогоднішній усі реальні обчислювальні пристрої можна змоделювати як машини зі скінченою кількістю станів, оскільки всі реальні комп'ютери працюють на скінчених ресурсах. Така машина має набір станів і набір переходів, на які впливає потік вхідних даних. Деякі стани визначені кінцевими. Вхідний потік подається в машину одним символом за раз, переходи між станами порівнюються з вхідним символом, і якщо є відповідний перехід, машина переходить в новий стан. Якщо в кінці вхідного потоку машина знаходиться в кінцевому стані, то увесь вхідний потік є таким, що приймається даною машиною.
- Недетермінований скінчений автомат
- Інша проста модель обчислення, хоча послідовність її виконання не визначена однозначно. Вона може бути інтерпретована як одночасне виконання декількох варіантів обчислення з використанням кінцевого числа станів. Однак можна довести, що будь-який недетермінований автомат зводиться до еквівалентного йому детермінованого.
- Автомат з магазинною пам'яттю
- Подібний до кінцевого автомата, за винятком того, що він має стек, якому дозволено зростати до довільного розміру. Переходи станів додатково вказують, чи слід додавати символ до стека або вилучати символ зі стека. Ця модель є більш потужною, ніж кінцевий автомат завдяки своєму нескінченному стеку (пам'яті), хоча тільки верхній елемент стека доступний в окремий момент часу.
Див. також
Джерела
- (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN . Part Two: Computability Theory, Chapters 3–6, pp. 123–222.
- Christos Papadimitriou (1993). Computational Complexity (вид. 1st). Addison Wesley. ISBN . Chapter 3: Computability, pp. 57–70.
- (2004). Computability Theory (вид. 1st). Chapman & Hall/CRC. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Obchislyuvanist vlastivist zadachi buti efektivno rozv yazanoyu Ce klyuchova tema v oblasti teoriyi obchislyuvanosti v ramkah matematichnoyi logiki i teoriyi algoritmiv u informatici Obchislyuvanist zadachi tisno pov yazana z zadacheyu isnuvannya algoritmu dlya yiyi virishennya Najbilsh shiroko vivchenimi modelyami obchislyuvanosti ye Tyuring obchislyuvalni i m rekursivni funkciyi ta lyambda chislennya vsi z nih mayut parno ekvivalentnu obchislyuvalnu potuzhnist algoritmi pobudovani dlya odniyeyi sistemi mayut vidpovidniki u inshih Doslidzhuyutsya j inshi formi obchislyuvanosti v teoriyi avtomativ vivchayutsya ponyattya obchislyuvanosti yaki slabkishi za mashini Tyuringa todi yak oblasti giperobchislen vivchayutsya silnishi ponyattya obchislyuvanosti ZadachiCentralnoyu ideyeyu teoriyi ye en yaka ye praktichnim zavdannyam chiyu obchislyuvanist mozhna vivchati Isnuye dva klyuchovih tipi problem Problema viboru fiksuye nabir S yakim mozhe buti nabir ryadkiv naturalnih chisel chi inshih ob yektiv vzyatih z deyakogo bilshogo naboru U Problema polyagaye u tomu chi zadanij element u z U nalezhit S Napriklad U mnozhina naturalnih chisel i S mnozhina prostih chisel vidpovidnij zadachi viboru vidpovidaye test na prostotu Funkcionalna problema skladayetsya z funkciyi f u yakoyu U ye mnozhinoyu viznachennya a V mnozhinoyu znachen Dana problema obchislyuye dlya danogo elementa u z U vidpovidnij element f u z V Napriklad U i V mozhut buti mnozhinoyu vsih skinchenih dvijkovih ryadkiv todi yak f mozhe prijmati ryadok i povertati ryadok u zvorotnomu poryadku napriklad f 0101 1010 Inshi tipi problem vklyuchayut v sebe zadachu poshuku ta zadachu optimizaciyi Odna z cilej teoriyi obchislyuvanosti polyagaye u viznachenni yaki problemi abo klasi problem mozhna virishiti v kozhnij z modelej obchislennya Formalni modeli obchislenModel obchislennya ce formalnij opis osoblivogo tipu obchislyuvalnogo procesu Takij opis chasto maye formu abstraktnoyi mashini yaka priznachena dlya vikonannya postavlenogo zavdannya Do zagalno vidomih modelej obchislennya ekvivalentnim mashini Tyuringa div tezu Chercha Tyuringa nalezhat Lyambda chislennya Obchislennya skladayetsya z pochatkovogo lyambda virazu abo dvoh yaksho vi hochete vidokremiti funkciyu ta jogo vhidni dani ta kinceva poslidovnist lyambda termiv kozhen z yakih vivedeno z poperednogo termu zastosuvannyam beta redukciyi Kombinatorna logika Koncepciya sho maye bagato spilnogo z lyambda chislennyam ale yaka maye vazhlivi vidminnosti napriklad kombinator fiksovanoyi tochki Y maye normalnu formu v kombinatornij logici ale ne v lyambda chislenni Kombinatorna logika rozvivalasya mayuchi veliki ambiciyi otrimati rozuminnya prirodi paradoksiv zrobiti osnovi matematiki bilsh ekonomnimi konceptualno usunuti ponyattya zminnoyi takim chinom utochnivshi yiyi rol v matematici m rekursivni funkciyi Obchislennya skladayetsya z m rekursivnoyi funkciyi tochnishe z poslidovnosti yaka yiyi viznachaye bud yakogo vhidnogo znachennya i poslidovnosti rekursivnih funkcij sho z yavlyayutsya u viznachenij poslidovnosti z vhodami i vihodami Takim chinom yaksho v viznachalnij poslidovnosti rekursivnoyi funkciyi f x z yavlyayutsya funkciyi g x i h x y to mozhut z yavitisya termi vidu g 5 7 abo h 3 2 10 Kozhen zapis u cij poslidovnosti povinen buti zastosuvannyam bazovoyi funkciyi abo buti naslidkom z vishezaznachenih zapisiv vikoristovuyuchi kompoziciyu primitivnu rekursiyu abo m rekursiyu Napriklad yaksho f x h x g x to dlya poyavi f 5 3 termi g 5 6 i h 3 6 3 povinni z yavitisya vishe u poslidovnosti Obchislennya pripinyayetsya tilki v tomu vipadku yaksho ostannij term vidaye znachennya rekursivnoyi funkciyi en Vklyuchayut algoritmi Markova yaki vikoristovuyut pravila shozhi na pravila gramatik dlya roboti nad ryadkami simvoliv takozh chislennya Posta Registrova mashina Teoretichno cikava idealizaciya komp yutera Isnuye dekilka yiyi variantiv U bilshosti z nih kozhen reyestr mozhe mistiti naturalne chislo neobmezhenogo rozmiru a instrukciyi prosti i malochiselni napriklad mashina de isnuyut tilki zmenshennya na odinicyu u poyednanni z umovnim stribkom zbilshennya na odinicyu i zupinka mashini Vidsutnist neskinchennoyi abo dinamichno zrostayuchoyi mnozhini registriv yaku mozhna pobachiti na mashinah Tyuringa mozhna zrozumiti zaminivshi yiyi rol tehnikoyu numeraciyi Gedelya toj fakt sho kozhen reyestr maye naturalne chislo daye mozhlivist predstaviti skladnu rich napriklad poslidovnist abo matricyu za dopomogoyu vidpovidnogo velicheznogo naturalnogo chisla odnoznachnist yak predstavlennya tak i interpretaciyi vstanovlyuyutsya chislovoyu teoriyeyu osnov cih metodiv Mashina Tyuringa Shozha na kincevij avtomat za vinyatkom togo sho vhid podayetsya na strichci yaku mashina Tyuringa mozhe chitati perezapisuvati i po yakij mozhe vilno poslidovno peremishatisya tobto ne mozhe pereskakuvati komirki strichki Strichci dozvoleno zrostati do dovilnogo rozmiru Mashina Tyuringa zdatna vikonuvati skladni obchislennya yaki mozhut mati dovilnu trivalist Cya model ye mabut najvazhlivishoyu modellyu obchislen u komp yuternij nauci oskilki vona imituye obchislennya za vidsutnosti viznachenih obmezhen resursiv en Mashina mozhe mati bilshe odniyeyi strichki krim togo mozhe buti kilka golovok na odnu strichku Nespodivano bud yake obchislennya yake mozhe buti vikonane cim rodom mashini takozh mozhe buti vikonane zvichajnoyu mashinoyu Tyuringa hocha ostannya mozhe buti povilnishoyu abo vimagati bilshe miscya dlya strichki P Yak i mashini Tyuringa P vikoristovuye neskinchennu strichku simvoliv bez dovilnogo dostupu i dosit minimalistichnij nabir instrukcij Ale ci instrukciyi duzhe rizni takim chinom na vidminu vid mashin Tyuringa P ne potribno pidtrimuvati okremij stan tomu sho vsya funkcionalnist zalezhna vid pam yati mozhe buti zabezpechena odniyeyu strichkoyu Zamist togo shob perepisuvati potochnij simvol vona mozhe vikonati dlya nogo operaciyu modulnoyi sumi z odiniceyu P maye takozh paru instrukcij cikliv ta dlya perevirki na porozhnij simvol Nezvazhayuchi na svij minimalistichnij harakter cya mashina stala batkivskoyu formalnoyu movoyu dlya movi programuvannya pid nazvoyu Brainfuck Na dodatok do zagalno vidomih obchislyuvalnih modelej isnuyut deyaki bilsh prosti obchislyuvalni modeli yaki korisni dlya specifichnih obmezhenih zastosuvan Regulyarni virazi napriklad viznachayut shabloni ryadkiv u bagatoh kontekstah vid programnogo zabezpechennya dlya ofisnoyi roboti do mov programuvannya Insha formalna matematichno ekvivalentna regulyarnim virazam struktura skinchenni avtomati vikoristovuyetsya v shemotehnici i v deyakih rishennyah zadach Kontekstno vilni gramatiki zadayut sintaksis mov programuvannya Nedeterminovanij avtomat z magazinnoyu pam yattyu she odna formalna struktura ekvivalentna kontekstno vilnim gramatikam Rizni modeli obchislen mayut rizni mozhlivosti vikonuvati rizni zavdannya Odnim iz sposobiv vimiryuvannya potuzhnosti obchislyuvalnoyi modeli ye vivchennya klasu formalnih mov yaki mozhe generuvati model takim chinom otrimuyetsya iyerarhiya mov Chomski Inshi obmezheni modeli obchislennya vklyuchayut Determinovanij skinchenij avtomat Na sogodnishnij usi realni obchislyuvalni pristroyi mozhna zmodelyuvati yak mashini zi skinchenoyu kilkistyu staniv oskilki vsi realni komp yuteri pracyuyut na skinchenih resursah Taka mashina maye nabir staniv i nabir perehodiv na yaki vplivaye potik vhidnih danih Deyaki stani viznacheni kincevimi Vhidnij potik podayetsya v mashinu odnim simvolom za raz perehodi mizh stanami porivnyuyutsya z vhidnim simvolom i yaksho ye vidpovidnij perehid mashina perehodit v novij stan Yaksho v kinci vhidnogo potoku mashina znahoditsya v kincevomu stani to uves vhidnij potik ye takim sho prijmayetsya danoyu mashinoyu Nedeterminovanij skinchenij avtomat Insha prosta model obchislennya hocha poslidovnist yiyi vikonannya ne viznachena odnoznachno Vona mozhe buti interpretovana yak odnochasne vikonannya dekilkoh variantiv obchislennya z vikoristannyam kincevogo chisla staniv Odnak mozhna dovesti sho bud yakij nedeterminovanij avtomat zvoditsya do ekvivalentnogo jomu determinovanogo Avtomat z magazinnoyu pam yattyu Podibnij do kincevogo avtomata za vinyatkom togo sho vin maye stek yakomu dozvoleno zrostati do dovilnogo rozmiru Perehodi staniv dodatkovo vkazuyut chi slid dodavati simvol do steka abo viluchati simvol zi steka Cya model ye bilsh potuzhnoyu nizh kincevij avtomat zavdyaki svoyemu neskinchennomu steku pam yati hocha tilki verhnij element steka dostupnij v okremij moment chasu Div takozhTeoriya avtomativ Avtomat en Teoriya skladnosti obchislen en Dzherela 1997 Introduction to the Theory of Computation PWS Publishing ISBN 0 534 94728 X Part Two Computability Theory Chapters 3 6 pp 123 222 Christos Papadimitriou 1993 Computational Complexity vid 1st Addison Wesley ISBN 0 201 53082 1 Chapter 3 Computability pp 57 70 2004 Computability Theory vid 1st Chapman amp Hall CRC ISBN 978 1 58488 237 4