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

нема опису редагування
м (Anticop перейменував сторінку з Обчислюванність на Обчислюваність)
'''Обчислюваність''' - — це властивість задачі бути ефективно роз'язаною. Це ключова тема в області [[Теорія обчислюваності|теорії обчислюваності]] в рамках [[Математична логіка|математичної логіки]] і [[Теорія алгоритмів|теорії алгоритмів]] у [[Інформатика|інформатиці]]. Обчислюваність задачі тісно пов'язана з задачею існування [[Алгоритм|алгоритму]] для її вирішення.
 
Найбільш широко вивченими моделями обчислюваності є [[Машина Тюрінга|Тьюрінг-обчислювальні]] і {{Не перекладено|μ-рекурсивна функція|μ-рекурсивні функції|en|μ-recursive function}}, та [[лямбда-числення]], всі з них мають парно еквівалентну обчислювальну потужність (алгоритми побудовані для однієї системи мають відповідники у інших). Досліджуються й інші форми обчислюваності: в [[Теорія автоматів|теорії автоматів]] вивчаються поняття обчислюваності, які слабкіші за машини Тьюринга, тоді як області [[Гіперобчислення|гіперобчислень]] вивчаються сильніші поняття обчислюваності.
'''Обчислюваність''' - це властивість задачі бути ефективно роз'язаною. Це ключова тема в області [[Теорія обчислюваності|теорії обчислюваності]] в рамках [[Математична логіка|математичної логіки]] і [[Теорія алгоритмів|теорії алгоритмів]] у [[Інформатика|інформатиці]]. Обчислюваність задачі тісно пов'язана з задачею існування [[Алгоритм|алгоритму]] для її вирішення.
 
Найбільш широко вивченими моделями обчислюваності є [[Машина Тюрінга|Тьюрінг-обчислювальні]] і {{Не перекладено|μ-рекурсивна функція|μ-рекурсивні функції|en|μ-recursive function}}, та [[лямбда-числення]], всі з них мають парно еквівалентну обчислювальну потужність (алгоритми побудовані для однієї системи мають відповідники у інших). Досліджуються й інші форми обчислюваності: в [[Теорія автоматів|теорії автоматів]] вивчаються поняття обчислюваності, які слабкіші за машини Тьюринга, тоді як області [[Гіперобчислення|гіперобчислень]] вивчаються сильніші поняття обчислюваності.
 
== Задачі ==
Центральною ідеєю теорії є {{Не перекладено|Обчислювальна проблема|обчислювальна проблема|en|Computational problem}}, яка є практичним завданням, чию обчислюваність можна вивчати.
 
Існує два ключових типи проблем:
 
* [[Проблема вибору]] фіксує набір ''S'', яким може бути набір рядків, натуральних чисел чи інших об'єктів, взятих з деякого більшого набору ''U.'' Проблема полягає у тому, чи заданий елемент ''u'' з ''U'' належить ''S.'' Наприклад, ''U'' - — множина натуральних чисел і ''S'' множина простих чисел, відповідній задачі вибору відповідає [[Тест простоти|тест на простоту]].
* [[Функціональна проблема]] складається з функції ''f'', у якою ''U'' є множиною визначення, а ''V''  — множиною значень''.'' Дана проблема обчислює для даного елемента ''u'' з ''U'' відповідний елемент ''f''(''u'') з ''V.'' Наприклад, ''U'' і ''V'' можуть бути множиною всіх скінчених двійкових рядків, тоді як ''f'' може приймати рядок і повертати рядок у зворотньому порядку (наприклад, f(0101) = 1010).
 
Інші типи проблем включають в себе задачу пошуку та [[Задача оптимізації|задачу оптимізації]] .
 
Одна з цілей теорії обчислюваності полягає у визначенні, які проблеми або класи проблем можна вирішити в кожній з моделей обчислення.
 
== Формальні моделі обчислень ==
[[Модель обчислення]]  — це формальний опис особливого типу обчислювального процесу. Такий опис часто має форму [[Автомат (дискретна математика)|абстрактної машини]], яка призначена для виконання поставленого завдання. До загально відомих моделей обчислення, еквівалентним [[Машина Тюрінга|машині Тьюринга]] (див. [[Теза Черча — Тюрінга|тезу Черча-Тьюрінга]] ), належать:
 
; [[Лямбда-числення]]: Обчислення складається з початкового лямбда-виразу (або двох, якщо ви хочете відокремити функцію та його вхідні дані) та кінцева послідовність лямбда термів, кожен з яких виведен з попереднього терму застосуванням [[Лямбда-числення|бета-редукції]].
; [[Лямбда-числення]]
; [[Комбінаторна логіка]]: Концепція, що має багато спільного з лямбда-численням, але яка має важливі відмінності (наприклад, комбінатор фіксованої точки '''Y''' має нормальну форму в комбінаторній логіці, але не в лямбда-численні). Комбінаторна логіка розвивалася маючи великі амбіції: отримати розуміння природи парадоксів, зробити основи математики економічнішими (концептуально), усунути поняття змінної (таким чином, уточнивши її роль в математиці).
: Обчислення складається з початкового лямбда-виразу (або двох, якщо ви хочете відокремити функцію та його вхідні дані) та кінцева послідовність лямбда термів, кожен з яких виведен з попереднього терму застосуванням [[Лямбда-числення|бета-редукції]].
; μ-рекурсивні функції: Обчислення складається з μ-рекурсивної функції, точніше, її визначаючої послідовності, будь-якого вхідного значення і послідовності рекурсивних функцій, що з'являються в визначеній послідовності з входами і виходами. Таким чином, якщо в визначальній послідовності рекурсивної функції {{Math|''f''(''x'')}} з'являються функції {{Math|''g''(''x'')}} і {{Math|''h''(''x'',''y'')}}, то можуть з'явитися терми виду {{Math|''g''(5) {{=}} 7}} або {{Math|''h''(3,2) {{=}} 10}}. Кожен запис у цій послідовності повинен бути застосуванням базової функції або бути наслідком з вищезазначених записів, використовуючи [[Композиція функцій|композицію]], [[Рекурсивні функції|примітивну рекурсію]] або {{Не перекладено|μ-рекурсивна функція|μ-рекурсію|en|μ-recursive function}}. Наприклад, якщо {{Math|''f''(''x'') {{=}} ''h''(''x'',''g''(''x''))}}, то для появи {{Math|''f''(5) {{=}} 3}}, терми {{Math|''g''(5) {{=}} 6}} і {{Math|''h''(3,6) {{=}} 3}} повинні з'явитися вище у послідовності. Обчислення припиняється тільки в тому випадку, якщо останній терм видає значення рекурсивної функції.
; [[Комбінаторна логіка]]
; {{Не перекладено|Система перезапису рядків|Системи перезапису рядків|en|Semi-Thue system}}
: Концепція, що має багато спільного з лямбда-численням, але яка має важливі відмінності (наприклад, комбінатор фіксованої точки '''Y''' має нормальну форму в комбінаторній логіці, але не в лямбда-численні). Комбінаторна логіка розвивалася маючи великі амбіції: отримати розуміння природи парадоксів, зробити основи математики економічнішими (концептуально), усунути поняття змінної (таким чином, уточнивши її роль в математиці).
: Включають [[Нормальні алгоритми|алгоритми Маркова]], які використовують правила схожі на правила [[Граматика|граматик]] для роботи над [[Рядок (програмування)|рядками]] символів; також [[числення Поста]].
; μ-рекурсивні функції
; [[Машина з натуральнозначними регістрами|Регістрова машина]]: Теоретично цікава ідеалізація комп'ютера. Існує декілька її варіантів. У більшості з них кожен реєстр може містити натуральне число необмеженого розміру, а інструкції прості і малочисельні, наприклад, машина, де існують тільки зменшення на одиницю (у поєднанні з умовним стрибком), збільшення на одиницю і зупинка мишини. Відсутність нескінченної (або динамічно зростаючої) множини регістрів (яку можна побачити на машинах Тьюринга) можна зрозуміти, замінивши її роль технікою [[Нумерація Геделя|нумерації Гёделя]]: той факт, що кожен реєстр має натуральне число, дає можливість представити складну річ (наприклад послідовність або матрицю) за допомогою відповідного величезного натурального числа  — однозначність як представлення, так і інтерпретації встановлюються [[Теорія чисел|числовою теорією]] основ цих методів.
: Обчислення складається з μ-рекурсивної функції, точніше, її визначаючої послідовності, будь-якого вхідного значення і послідовності рекурсивних функцій, що з'являються в визначеній послідовності з входами і виходами. Таким чином, якщо в визначальній послідовності рекурсивної функції {{Math|''f''(''x'')}} з'являються функції {{Math|''g''(''x'')}} і {{Math|''h''(''x'',''y'')}}, то можуть з'явитися терми виду {{Math|''g''(5) {{=}} 7}} або {{Math|''h''(3,2) {{=}} 10}}. Кожен запис у цій послідовності повинен бути застосуванням базової функції або бути наслідком з вищезазначених записів, використовуючи [[Композиція функцій|композицію]], [[Рекурсивні функції|примітивну рекурсію]] або {{Не перекладено|μ-рекурсивна функція|μ-рекурсію|en|μ-recursive function}}. Наприклад, якщо {{Math|''f''(''x'') {{=}} ''h''(''x'',''g''(''x''))}}, то для появи {{Math|''f''(5) {{=}} 3}}, терми {{Math|''g''(5) {{=}} 6}} і {{Math|''h''(3,6) {{=}} 3}} повинні з'явитися вище у послідовності. Обчислення припиняється тільки в тому випадку, якщо останній терм видає значення рекурсивної функції.
; [[Машина Тюрінга|Машина Тьюринга]]: Схожа на кінцевий автомат, за винятком того, що вхід подається на стрічці, яку машина Тьюринга може читати, перезаписувати і по якій може вільно '''послідовно''' переміщатися (тобто не може перескакувати комірки стрічки). Стрічці дозволено зростати до довільного розміру. Машина Тьюринга здатна виконувати складні обчислення, які можуть мати довільну тривалість. Ця модель є, мабуть, найважливішою моделлю обчислень у комп'ютерній науці, оскільки вона імітує обчислення за відсутності визначених обмежень ресурсів.
; {{Не перекладено|Система перезапису рядків|Системи перезапису рядків|en|Semi-Thue system}}
; {{Не перекладено|Багатострічкова машина Тюрінга|Машина Тьюринга з декількома стрічками|en|Multitape Turing machine}}
: Включають [[Нормальні алгоритми|алгоритми Маркова]], які використовують правила схожі на правила [[Граматика|граматик]] для роботи над [[Рядок (програмування)|рядками]] символів; також [[числення Поста]].
: Машина може мати більше однієї стрічки; крім того, може бути кілька головок на одну стрічку. Несподівано, будь-яке обчислення, яке може бути виконане цим родом машини, також може бути виконане звичайною машиною Тьюрінга, хоча остання може бути повільнішою або вимагати більше місця для стрічки.
; [[Машина з натуральнозначними регістрами|Регістрова машина]]
; {{Не перекладено|P′′|P′′|en|P′′}}
: Теоретично цікава ідеалізація комп'ютера. Існує декілька її варіантів. У більшості з них кожен реєстр може містити натуральне число необмеженого розміру, а інструкції прості і малочисельні, наприклад, машина, де існують тільки зменшення на одиницю (у поєднанні з умовним стрибком), збільшення на одиницю і зупинка мишини. Відсутність нескінченної (або динамічно зростаючої) множини регістрів (яку можна побачити на машинах Тьюринга) можна зрозуміти, замінивши її роль технікою [[Нумерація Геделя|нумерації Гёделя]]: той факт, що кожен реєстр має натуральне число, дає можливість представити складну річ (наприклад послідовність або матрицю) за допомогою відповідного величезного натурального числа — однозначність як представлення, так і інтерпретації встановлюються [[Теорія чисел|числовою теорією]] основ цих методів.
: Як і машини Тьюрінга, P′′ використовує нескінченну стрічку символів (без довільного доступу) і досить мінімалістичний набір інструкцій. Але ці інструкції дуже різні, таким чином, на відміну від машин Тьюрінга, P′′не потрібно підтримувати окремий стан, тому що вся функціональність, пзалежнапвід ам'яті, може бути забезпечена тоднієюслиш трічкою. Замість того, щоб переписувати поточний символ, вона може виконати для нього опреацію [[Модульна арифметика|модульної суми]] з одиницею. P′′ має також пару інструкцій циклів, та для перевірки на порожній символ. Незважаючи на свій мінімалістичний характер, ця машина стала батьківською формальною мовою для мови програмування під назвою [[Brainfuck]].
; [[Машина Тюрінга|Машина Тьюринга]]
: Схожа на кінцевий автомат, за винятком того, що вхід подається на стрічці, яку машина Тьюринга може читати, перезаписувати і по якій може вільно '''послідовно''' переміщатися (тобто не може перескакувати комірки стрічки). Стрічці дозволено зростати до довільного розміру. Машина Тьюринга здатна виконувати складні обчислення, які можуть мати довільну тривалість. Ця модель є, мабуть, найважливішою моделлю обчислень у комп'ютерній науці, оскільки вона імітує обчислення за відсутності визначених обмежень ресурсів.
; {{Не перекладено|Багатострічкова машина Тюрінга|Машина Тьюринга з декількома стрічками|en|Multitape Turing machine}}
: Машина може мати більше однієї стрічки; крім того, може бути кілька головок на одну стрічку. Несподівано, будь-яке обчислення, яке може бути виконане цим родом машини, також може бути виконане звичайною машиною Тьюрінга, хоча остання може бути повільнішою або вимагати більше місця для стрічки.
; {{Не перекладено|P′′|P′′|en|P′′}}
: Як і машини Тьюрінга, P′′ використовує нескінченну стрічку символів (без довільного доступу) і досить мінімалістичний набір інструкцій. Але ці інструкції дуже різні, таким чином, на відміну від машин Тьюрінга, P′′не потрібно підтримувати окремий стан, тому що вся функціональність, пзалежнапвід ам'яті, може бути забезпечена тоднієюслиш трічкою. Замість того, щоб переписувати поточний символ, вона може виконати для нього опреацію [[Модульна арифметика|модульної суми]] з одиницею. P′′ має також пару інструкцій циклів, та для перевірки на порожній символ. Незважаючи на свій мінімалістичний характер, ця машина стала батьківською формальною мовою для мови програмування під назвою [[Brainfuck]].
 
== Див. також ==
 
* [[Теорія автоматів]]
* [[Автомат (дискретна математика)|Автомат]]
* [[List of undecidable problems|Список невирішених проблем обчислюваності]]
* [[Теорія складності обчислень]]
* [[Computability logic|Логіка обчислюваності]]
[[Категорія:Теорія алгоритмів]]
[[Категорія:Теорія складності обчислень]]
21 091

редагування