7.Теза Черча-Тьюринга

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

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

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

8.Універсальність найпростішої мови програмування

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

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

9.Необчислювані функції

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

12.НП-задачі

В теорії алгоритмів NP-повна задача — задача із класу NP, в якій можна звести любу другу задачу із класу NP за поліноміальноє время. Таким чином, NP-повні задачі показують підмножину «самих важчих» задач в класі NP; і якщо буде знайдений «швидкий» алгоритм вирішення, то і люба друга задача із класу NP може бути вирішена так само «швидко».Завдання називається NP-повною в сильному сенсі, якщо у неї існує підзадача, яка:

-не є завданням з числовими параметрами,

-належить класу NP,

-є NP-повною.