Меню
Головна
 
Головна arrow Філософія arrow Історія, філософія і методологія техніки та інформатики
< Попередня   ЗМІСТ   Наступна >

Вычислимая функція і теза Черча - Тюрінга. Проблема гипервычислений

Деякі дослідники вважають, що новації є результатом спонтанних осяянь. Стосовно до інформатики це уявлення явно помилково: вона стала найвищою мірою закономірним результатом розвитку наук, насамперед логіки, математики та електроніки. Звернемося у зв'язку з цим до історії розвитку логіки та математики.

Історичний екскурс

Готфрід Лейбніц у XVII ст. поставив завдання вироблення універсального формалізованої мови, який можна було б використовувати при машинних обчислень. Однак для актуалізації його ідеї знадобилося два століття. Багато в чому це відбулося завдяки необхідності впоратися з парадоксами теорії множин, яка на початку XX ст. самої універсальної математичної наукою. Парадокси викликали до життя кілька проектів їх подолання, зокрема логицизм Б. Рассела, интуиционизм Л. Брауера і формалізм Д. Гільберта. Англієць Бертран Рассел розвинув теорію типів, виявилася досить актуальною для інформатики. Голландець Лейтзен Брауер заклав наріжний камінь у фундамент будівлі конструктивної логіки і математики, без якої неможливо уявити сучасну інформатику. Але особливо значущими виявилися для неї погляди Давида Гільберта. Німецький вчений вважав, що будь-яка математична і логічна система повинна бути представлена у вигляді формального мови з завданням відповідних аксіом і правил виводу. Правомірність такої системи обґрунтовується в метаматематике, для чого доводиться повнота системи аксіом і несуперечність процесу виведення теорем.

Такими були вихідні інтуїції Гільберта. Розмірковуючи над ними, він прийшов до висновку, що вимога повноти системи аксіом і несуперечності доказів слід доповнити концептами розв'язності і обчислюваності. Формула вирішувана, якщо в даній формальній системі доказові або вона сама, або її заперечення. Функція вычислима, якщо існує алгоритм (тобто кінцева послідовність операцій), переробний всякий об'єкт х, для якого задана функція/об'єкт/(х) і не застосовний до будь-якого х, для якого/ не визначена. Вважається, що проблема розв'язності була в чіткій формі представлена Давидом Гильбертом і Вільгельмом Аккерманом в 1928 р. 1 Наступні відкриття мали для доль інформатики виняткову значимість. У 1931 р. австрієць Курт Гедель довів неповноту будь-якої формальної системи, що містить значну частину формальної арифметики, при цьому він використовував поняття рекурсивної функции2. У 1936 р. р. американець Алонзо Черч розробив теорію лямбда-числення, а також підтвердив існування нерозв'язних завдань. У тому ж році англієць Алан Тьюринг запропонував алгоритм здійснення ефективної обчислюваності, сопрягаемый з концептом абстрактної математичної машини. Подібно Геделю і Креслю Тьюринг підтвердив наявність не тільки розв'язних, але і нерозв'язних функцій. Роботи американського вченого Стівена Кліні мали найважливіше значення для теорії формальних мов, а Еміль Пост удосконалив концепт абстрактної математичної машини.

Дослідження Геделя, Черча, Тюрінга, Кліні і Посади, доповнені в кінці 1947 р. теорією нормальних алгоритмів А. А. Маркова, склали основу інформатики. Найголовніше полягало в тому, що у значною мірою був визначений механізм обчислення, яке стало розумітися як здійснення операцій з символами, що закінчується отриманням ефективного результату. Повною мірою було усвідомлено існування як розв'язних, так і нерозв'язних завдань. Але навіть останні, як показало осмислення теореми Геделя про неповноту, нерозв'язні лише за певних умов: при відповідній зміні завдання можуть стати розв'язання. Наприклад, як свідчать роботи Герхарда Генцена, формалізована арифметика несуперечлива і повна в разі опори на індукцію до деякого рахункового трансфинитного числа. Таким чином, проблема нерозв'язності завжди є незавершеною історією.

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

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

Цікаво простежити за процесом осмислення концепту обчислюваності.

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

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

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

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

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

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

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

Однак і критики тези Черча - Тюрінга зустрілися з відомими труднощами. Пропонувались все нові варіанти ефективно вычислимых функцій, зокрема в теоріях Е. Поста (канонічні системи) і А. А. Маркова (нормальні алгоритми), використовувалася також комбінаторна логіка X. Каррі. Тим не менш завжди з'ясовувалося, що зазначені методи сумісні з уявленнями про рекурсивних функцій, лямбда-численні і машині Тюрінга. Пропонувалися різні варіанти абстрактних машин, зокрема, варіювалися їх уявні конструкти, наприклад кількість стрічок і конфігурація прочитуючих головок. І знову незмінно виявлялося, що ці вдосконалені машини не скасовують ті концепти, які ввів Тюрінг. Нарешті, зверталася увага на обмеження, які привносять із собою безпосередньо ті процеси, що відбуваються в реальних комп'ютерах. Тут, зокрема, необхідно враховувати кінцівку швидкості передачі сигналів і обмежене число елементів пам'яті. Але і в цьому випадку залишалося в силі стало в інформатиці ортодоксальним уявлення про ефективно обчислюваною функції, заснованій на прийнятті тези Черча - Тюрінга.

Вся справа в тому, що рекурсивні функції, лямбда-числення і машина Тюрінга являють собою не тотожні, а родинні (подібні) концептуальні освіти. Їх схожість не виключає розходжень. Відомо, наприклад, що специфіка лямбда-числення полягає в його високого ступеня абстрактності. Це стало підставою для створення мови ЛИСП. Машини Тюрінга, незважаючи на їх формально-математичний характер, звернені до механічних процесів. Рекурсивні функції значно більш виразно, ніж машини Тьюринга і лямбда-числення, співвідносяться безпосередньо з арифметичними діями. Таким чином, на наш погляд, у формулюванні тези Черча - Тюрінга мова повинна йти не про тотожність, а про схожість трьох розумінь ефективності обчислювальних операцій. З урахуванням даної обставини теза Черча - Тьюринга може бути переформулирован наступним чином: ефективно вычислимая функція існує принаймні в трьох схожих і доповнюючих один одного видах - у формі рекурсивних функцій, лямбда-числення і машини Тюрінга.

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

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

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

Теоретична розробка

1. Процес може бути використано у математичних цілях, якщо і тільки якщо його поведінка на вході/виході:

а) або детерминистично, або приблизно детерминистично і викликається їм помилка може бути зведена до довільно малої величині;

б) визначається за кінцеве число кроків.

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

Сенс двох наведених вище тез полягає в обґрунтуванні можливості сверхтьюринговых машин, здатних здійснювати гипервычисления. Основний напрямок пошуку пов'язано з урахуванням різноманіття фізичних процесів, оскільки постулюється, що фундаментом інформатики є не тільки математика, а й фізика. Існує кілька десятків проектів супертьюринговых машин. В одних випадках допускається введення інформації ще на стадії виконання програми, в інших робиться спроба відмовитися від лінійності часу: воно сповільнюється, прискорюється, замикається. Як відомо з фізики, такі процеси дійсно існують. Робляться спроби використовувати актуальну нескінченність: мається на увазі, що сума нескінченного числа членів може мати цілком певне значення. Звертається увага на необхідність використання імовірнісних процесів. Але найбільші надії покладаються на квантові комп'ютери, тому розглянемо їх природу більш уважно.

Міждисциплінарні зв'язки інформатики з фізикою

Квантова фізика, як відомо, у багатьох відносинах принципово відрізняється від своєї класичної попередниці. Ця обставина має для ідеї обчислень за допомогою квантових комп'ютерів вирішальне значення. Припустимо, що квантова система складається з Ь дворівневих квантових елементів, які називаються квантовими бітами, або кубітами. У такому разі вона має 21 станами, які змінюються у відповідності з рівнянням Шредінгера. Приймається, що еволюція квантового стану є процесом, що виконує обчислення. Отже, паралельно виконуються 21 операцій. У класичному випадку комп'ютер виконує одну операцію за одною. При зростанні числа I перевага квантового комп'ютера перед його класичним побратимом виявляється особливо виразно.

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

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

Підводячи підсумки аналізу проблеми гипервычислений, необхідно зазначити, що дана область досліджень перебуває у стадії становлення. М. Стэннет, розглянув два десятка варіантів гиперкомпьютеров, упевнений, що нової області досліджень належить майбутнє. Не існує жодних обмежень, які свідчили б на користь хибності ідеї. Гипервычисления відносяться до звичайних обчислень приблизно так само, як неевклідова геометрія до евклидовой2. Принципово іншу позицію займає американський математик М. Девіс. Він вважає, що прихильники гипервычислений некритично сприймають нехитрий теза про те, що якщо існує фізичний процес, що генерує невычислимую допомогою машини Тюрінга функцію або числа, то він може бути використаний для гипервычислений3. На думку Девіса, питання про необчислюваності некритично підмінений проблемою гипервычислимости. Втім, безсумнівно, що дослідження в області гипервычислений набирають темп. Зі свого боку зазначимо існування потреби в поглибленої концептуальної опрацювання концепції гипервычислений. Констатуємо, що поки ще парадигма обчислення, представлена блоком рекурсивних функцій, машиною Тьюрінга і лямбда-обчисленням, не отримала гідного суперника.

Висновки

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

2. Гостро відчувається потреба в поглибленої концептуальної опрацювання концепту гипервычислений.

 
< Попередня   ЗМІСТ   Наступна >

Схожі тими

Відтворювальна функція
Тезу про державно-монополистическом капіталізмі
Функція банкіра уряду
Спілкування як морально-психологічна проблема
Функції соціальної терапії
ФУНКЦІЇ ДЕРЖАВИ
Перевизначення основних проблем педагогічної психології
Проблема справедливості в розподілі
Соціально-етичні проблеми інформатики
Актуальні проблеми комп'ютерної етики
 
Предмети
Банківська справа
БЖД
Бухоблік і аудит
Документознавство
Екологія
Економіка
Етика і естетика
Інвестування
Інформатика
Історія
Культурологія
Література
Логістика
Маркетинг
Медицина
Менеджмент
Політологія
Політекономія
Право
Психологія
Соціологія
Страхова справа
Товарознавство
Філософія
Фінанси