Курсова робота
Поняття предиката. Безліч істинності предиката. Класифікація предикатів
Введення
Тьюринг обчислювальний предикат
Алан Тьюринг (Turing) в 1936 році опублікував у працях Лондонського математичного товариства статтю «Про вичіслімих числах в додатку до проблеми дозволу», яка нарівні з роботами Посту і Черча лежить в основі сучасної теорії алгоритмів.
Передісторія створення цієї роботи пов'язана з формулюванням Давидом Гільбертом на Міжнародному математичному конгресі в Парижі в 1900 році недозволених математичних проблем. Однією з них було завдання доказу несуперечності системи аксіом звичайної арифметики, яку Гільберт надалі уточнив як «проблему разрешимости» - знаходження загального методу, для визначення здійсненності даного висловлювання на мові формальної логіки.
Стаття Тьюринга якраз і давала відповідь на цю проблему - друга проблема Гільберта виявилася нерозв'язною. Але значення статті Тьюринга виходило далеко за рамки того завдання, з приводу якої вона була написана.
Наведемо характеристику цієї роботи, приналежну Джону Хопкрофта: «Працюючи над проблемою Гільберта, Тьюрингу довелося дати чітке визначення самого поняття методу. Відштовхуючись від інтуїтивного уявлення про метод як про якийсь алгоритмі, тобто процедурою, яка може бути виконана механічно, без творчого втручання, він показав, як цю ідею можна втілити у вигляді докладної моделі обчислювального процесу. Отримана модель обчислень, в якій кожен алгоритм розбивався на послідовність простих, елементарних кроків, і була логічною конструкцією, названої згодом машиною Тьюринга ».
Алан Тьюринг висловив припущення, що будь-який алгоритм в інтуїтивному сенсі цього слова може бути представлений еквівалентної машиною Тьюринга. Це припущення відомо як теза Черча-Тьюринга. Кожен комп'ютер може моделювати машину Тьюринга (операції перезапису елементів, порівняння і переходу до іншої сусідньої осередку з урахуванням зміни стану машини). Отже, він може моделювати алгоритми в будь-якому формалізмі, і з цієї тези випливає, що всі комп'ютери (незалежно від потужності, архітектури і т.д.) еквівалентні з точки зору принципової можливості вирішення алгоритмічних задач.
За час свого існування людство придумало безліч алгоритмів для вирішення різноманітних практичних і наукових проблем. Твердження про існування алгоритмічно нерозв'язних проблем є досить сильним - ми констатуємо, що ми не тільки зараз не знаємо відповідного алгоритму, але ми не можемо принципово ніколи його знайти.
Успіхи математики до кінця XIX століття привели до формування думки, яке висловив Д. Гільберт - «в математиці не може бути нерозв'язних проблем», у зв'язку з цим формулювання проблем Гильбертом на конгресі 1900 року в Парижі була керівництвом до дії, констатацією відсутності рішень в даний момент.
Першою фундаментальною теоретичною роботою, пов'язаною з доказом алгоритмічної нерозв'язності, була робота Курта Геделя - його відома теорема про неповноту символічних логік. Це була строго формулювати математична проблема, для якої не існує вирішального її алгоритму. Зусиллями різних дослідників список алгоритмічно нерозв'язних проблем був значно розширений. Зокрема, не існує алгоритму (машини Тьюринга), що дозволяє за описом довільного алгоритму і його вихідних даних (і алгоритм і дані задані символами на стрічці машини Тьюринга) визначити, чи зупиняється цей алгоритм на цих даних або працює нескінченно.
Фундаментально алгоритмічна нерозв'язність пов'язана з нескінченністю виконуваних алгоритмом дій, тобто неможливістю передбачити, що для будь-яких вихідних даних рішення буде отримано за кінцеве кількість кроків.
Розкриття питання - що таке машина Тьюринга, які завдання можна вирішувати з її допомогою і яким чином, є метою даної курсової роботи. Робота складається вступу, висновків, списку використаних джерел та двох глав. У першій - теоретичної, вводиться поняття машини Тьюринга, докладно розглядається принципи її роботи, розкриваються всі основні моменти, супутні даному поняттю: функцій, вичіслімих по Тьюрингу, еквівалентності машини Тьюринга поняттю «алгоритм», правила конструювання машин Тьюринга, композицій машин Тьюринга та ін. У другому розділі наведені вирішення завдань, реалізованих на машинах Тьюринга.
1. Машини Тюрінга
1.1 Визначення машини Тьюринга
Введення поняття машини Тьюринга стало однією з перших і вельми вдалих спроб дати точну мате...
