Розв’язання задач з елементів теорії алгоритмів та моделей обчислювання і за допомогою машин Тюрінга. Курсова робота з Основи дискретної математики. Робота № 524694

Перехід до торгівельного партнера Binance

Розв’язання задач з елементів теорії алгоритмів та моделей обчислювання і за допомогою машин Тюрінга

Інформація про навчальний заклад

ВУЗ:

Інші

Інститут:

Не вказано

Факультет:

Менеджмент

Кафедра:

Кафедра програмного забезпечення

Інформація про роботу

Рік:

2004

Тип роботи:

Курсова робота

Предмет:

Основи дискретної математики

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Інститут менеджменту та економіки „Галицька Академія” Кафедра програмного забезпечення та штучного інтелекту КУРСОВА РОБОТА з дисципліни: “Основи дискретної математики” Тема – Розв’язання задач з елементів теорії алгоритмів та моделей обчислювання і за допомогою машин Тюрінга. ПОЯСНЮВАЛЬНА ЗАПИСКА м. Івано-Франківськ 2004 Анотація В курсовій роботі проаналізовані основні поняття і властивості елементів теорії алгоритмів, функціонування моделей обчислювання та функціонування машин Тюрінга, і розв’язання певних типів задач. Summary In the term paper there are the analysed basic concepts and properties of elements of theory of algorithms, functioning of models of calculation and functioning of machines of Tjuringa. ЗМІСТ Вступ 1. Алгоритм Евкліда. 2. Властивості алгоритмів. 3. Універсальна машина Тюрінга. .......................................................... 3.1 Проблема зупину. ....................................................................... 3.2 Теза Тюрінга. Зв’язок рекурсивних функцій з машинами Тюрінга. ............................................................................................. 3.4 Алгоритмічна нерозв’язуваність і машини Тюрінга. .............. 4. Задача по теорії алгоритмів.......................................................... 5. Задачі по машинах Тюрінга. ........................................................ Висновок Перелік використаних літературних джерел.......................... Вступ З давніх часів у математиці склалося інтуїтивне уявлення про алгоритм як формальне розпорядження, що визначає сукупність операцій і порядок їх виконання для розв’язання задач деякого типу. Термін походить від латинізованої вимови (Algorithmi) імені середньовічного узбецького математика аль-Хорезмі, який ще в ІХ ст. сформулював правила, що дають змогу складати та розв’язувати квадратні рівняння. З алгоритмами, тобто ефективними процедурами, які однозначно приводять до результату, математика мала справу завжди й у своєму розвитку на копичила безліч різних алгоритмів. Дістаючи відповідну інтерпретацію в конкретних додатках, вони становлять значну і найсуттєвішу частину математичного апарату, який використовується в техніці. Відомі зі шкільної програми методи множення <<стовпчиком>> та ділення <<кутом>>, алгоритм Евкліда знаходження найбільшого спільного дільника двох додатних натуральних чисел. Алгоритм Евкліда Нехай задано цілі числа a і b. Знайти їх НСД. 1. Розглянути числа a і b. Перейти до наступного кроку. 2. Порівняти числа a і b (a = b; a > b; a < b). Перейти до наступного кроку. 3. Якщо a = b, то кожне з них є НСД. Кінець. Якщо ні, то перейти до наступного кроку. 4. Якщо a < b,то переставити їх місцями a > b і перейти до наступного кроку. 5. Знайти b- a і розглянути числа a – b. Перейти до кроку 2, і т. доки не дістанеться шуканий результат. Алгоритм Евкліда задано за допомогою найпростіших арифметичних операцій (віднімання, порівняння). Якщо розв’язування якої-небудь задачі зводиться до арифметичних дій, то відповідні алгоритми називають числовими. Алгоритм Евкліда – числовий. Поки математика мала справу в основному з числами й обчисленнями, а поняття алгоритму ототожнювалися з поняттям методу обчислення, необхідності у вивченні самого поняття розвитку загальної математики алгоритму не виникало. Традиції організації обчислень складалися віками і стали складовою частиною наукової культури в тій самій мірі, що й елементарні навички логічного мислення. У своєму накопичила величезну кількість алгоритмів, але все різноманіття обчислень комбінувалося з невеликого числа чітко визначених операцій арифметики, тригонометрії та аналізу. Тому поняття методу обчислення вважалося спочатку інтуїтивно зрозумілим і не потребувало спеціальних досліджень. Подальший процес розвитку обчислювальних методів сприяє ствердженню думки про те, що розв’язок будь-якої математичної проблеми має бути алгоритмічним. Такої думки, наприклад, дотримувались визначні математики Р. Декарт, Г. В. Лейбніц, Д. Гілберт. Останній активно стимулював алгоритмічні дослідження. Серед його знаменитих 23 проблем, сформульованих у 1900 р. На Міжнародному математичному конгресі, є десята проблема Гілберта: дано алгебричне рівняння f (, ..., )= 0 з цілими коефіцієнтами. Потрібно знайти метод, згідно з яким за допомогою скінченого числа операцій можна було б встановити, чи має це рівняння розв’язки в цілих числах. Метод, про який ідеться в цій проблемі, розуміють нині як алгоритм. У той час теорія алгоритмів ще не була створена і мова могла йти лише про позитивне вирішення цієї проблеми. Проте у 1970 р. радянський математик Ю. В. Матіясевич довів, що такого алгоритму не існує, хоча вперше віра в універсальність алгоритмічних методів була підірвана в 1931 р. працею К. Геделя “Про формально не розв’язувані вислови висловлення principia mathematica і споріднених систем”. У ній було показано, що є такі математичні проблеми, які не можуть бути розв’язані за допомогою алгоритмів із деякого точно визначеного класу алгоритмів. Таким чином, у теорії алгоритмів виникла зовсім нова ситуація. До того часу, поки математики вірили в можливість алгоритмічного розв’язання математичних задач, не виникла потреба уточнювати поняття алгоритму: якщо для розв’язання деякого класу задач пропонувався конкретний алгоритм, то вчені доходили згоди вважати його дійсно шуканим алгоритмом. І тільки доведення того, що не існує алгоритму для розв’язання певного класу задач, яке є висловлюванням про всі можливі алгоритми, потребує уточнення цього важливого поняття. Таким чином, до уточнення поняття “алгоритм”у математиці були поширені дві точки зору: 1. Усі проблеми є алгоритмічно розв’язуваними. Проте алгоритм для вирішення деяких з них не знайдено, тому що не вистачає засобів у сучасній математиці для його побудови. Прихильники цієї думки вважали, що для вирішення проблем, які називаються алгоритмічно нерозв’язуваними, просто не вистачає засобів сучасної математики, побудова шуканих алгоритмів – справа майбутнього. 2. Існують класи задач, для розв’язання яких узагалі не існує алгоритму, тобто деякі проблеми не можна вирішувати механічно за допомогою формальних міркувань й обчислень. Ці проблеми потребують творчого мислення. Це дуже сильне ствердження, адже воно поширюється на всі майбутні часи і засоби. Поки визначення алгоритму ґрунтувалось на інтуїтивному уявленні, про математичне доведення правоти другої думки не могло бути й мови. Завдяки появі гіпотез про існування стандартних форм, у яких можуть бути виражені будь-які алгоритми, стало можливим сформулювати поняття “алгоритм” та “алгоритмічно нерозв’язувана проблема” у точних математичних термінах. Починаючи з 1935 р., було запропоновано кілька уточнень поняття алгоритму. Математики погодились із тим, що уточнені поняття адекватно виражають інтуїтивне уявлення про алгоритм. Для цього є такі підстави: - доведено, що всі відомі на цей час уточнені поняття алгоритму еквівалентні між собою; - усі алгоритми в точному розумінні є алгоритмами в інтуїтивному розумінні; - усі відомі алгоритми в інтуїтивному розумінні можна “промоделювати” алгоритмами в точному розумінні. Довести адекватність інтуїтивного і точного понять алгоритмів неможливо тому, що не існує точного означення алгоритму в інтуїтивному розумінні. Досвід парадоксів теорії множин навчив математику обережно оперувати нескінченністю та, якщо це можливо, навіть про нескінченність міркувати за допомогою методів, в яких використовуються тільки скінченні множини скінченних об’єктів. З’ясування того, які об’єкти, а також які дії над ними можна вважати точно визначеними, які властивості та можливості мають комбінації елементарних дій, що можна і чого не можна робити за їх допомогою - все це стало предметом теорії алгоритмів та формальних систем, яка спочатку виникла в межах метаматематики і стала найважливішою її частиною. Основним внутрішнім математичним додатком теорії алгоритмів виявилися докази неможливості алгоритмічного(тобто точного й однозначного) розв’язання деяких математичних проблем. Такі докази (як і точні формулювання тверджень, що доводяться) нездійсненні без точного поняття алгоритму. У техніку термін “алгоритм” введено разом із терміном “кібернетика”. Якщо поняття методу обчислення не потребувало пояснень, то поняття процесу управління довелося формулювати практично заново. Знадобилося усвідомити, які вимоги має задовольняти послідовність дій, щоб вважатися конструктивно заданою, тобто мати право називатися алгоритмом. У цьому усвідомленні величезну допомогу інженерній інтуїції надала практика використання обчислювальних машин, що розбила поняття алгоритму відчутною реальністю. Традиційно процес розв’язування задачі на ЕОМ складається із таких етапів: постановка задачі, тобто чітке її формулювання із зазначенням мети, яку потрібно досягти. Тут виділяються початкові дані, результати і визначається зв’язок між початковими даними та результатами; - створення математичної моделі, тобто визначення математичних співвідношень(формул, рівнянь), що пов’язують результати з початковими даними; - розробка алгоритму розв’язання задачі, тобто побудова схеми цього процесу; - написання програми, тобто запис алгоритму розв’язання задачі мовою, зрозумілою ЕОМ; - налагодження програми, тобто пошук помилок у програмі й усунення їх; - розв’язання задачі на комп’ютері, тобто розрахунки за готовою програмою та аналіз одержаних результатів. У різних задачах деякі з перерахованих етапів можуть бути відсутні, деякі етапи можуть бути поділені на більше число, але схема залишається такою, як викладено вище. Чітке уявлення про те, що таке алгоритм, важливо не тільки для правильного слово використання. Воно потрібне також при розробленні конкретних алгоритмів, особливо коли мається на увазі їх подальше програмування. Проте це уявлення ще важливіше для наведення порядку в бурхливо зростаючому алгоритмічному господарстві. Щоб орієнтуватися в морі алгоритмів, яке захлиснуло технічну кібернетику, треба вміти порівнювати різні алгоритми озв’язання одних і тих самих задач, причому не тільки за якістю розв’язання, а й за характеристиками самих алгоритмів. Таке порівняння неможливе без уведення точної мови для обговорення всіх цих питань; іншими словами, самі алгоритми мають стати такими самими предметами точного дослідження, як і ті об’єкти, для роботи з якими вони призначені. Таким чином, можна сформулювати основні вимоги до алгоритмів. 1. Будь-який алгоритм застосовується для початкових даних видає результати. У технічних термінах це означає, що алгоритм має входи й виходи. Крім того, під час роботи алгоритму з’являються проміжні результати, що використовуються далі. Таким чином, кожний алгоритм має справу з даними початковими, проміжними і вихідними. Оскільки маємо намір уточнювати поняття алгоритму, треба уточнити також поняття даних, тобто зазначити, які вимоги мають задовольняти об’єкти, щоб з ними могли працювати алгоритми. Зрозуміло, що ці об’єкти мусять бути чітко визначені і відрізнятися як один від одного, так і від “не об’єктів”. У багатьох важливих випадках добре зрозуміло, що це означає: до таких алгоритмічних об’єктів належать числа, вектори, матриці суміжності графів, формули. Замість того, щоб намагатися дати загальне словесне означення чіткої визначеності об’єкта, в теорії алгоритмів фіксують конкретні скінченні набори початкових об’єктів та скінчений набір засобів побудови інших об’єктів з елементарних. Набір елементарних об’єктів утворюють скінчений алфавіт початкових символів, з яких будуються інші об’єкти; типовим засобом побудови є індуктивні означення, які показують, як будувати нові об’єкти з уже побудованих. Найпростіше індуктивне означення це означення деякої множини слів, класичним прикладом якого є означення ідентифікатора на мові Паскаль: ідентифікатор це або літера, або ідентифікатор, до якого приписано праворуч літеру чи цифру. Слова скінченої довжини в скінченних алфавітах(зокрема числа) звичайний тип алгоритмічних даних, а число символів у слові(довжина слова) природна одиниця обсягу інформації, що обробляється. Складнішим випадком алгоритмічних об’єктів є формули. Вони також визначаються індуктивно і також є словами у скінченному алфавіті, але не кожне слово в цьому алфавіті є формулою. У цьому випадку, як правило, основним алгоритмам початкові передують допоміжні, які перевіряють, чи задовольняють дані потрібні вимоги. Така перевірка називається синтаксичним аналізом. 2. Дані для їх розміщення потребують пам’яті. Пам’ять вважаєть- ся однорідною й дискретною, тобто складається з однакових комірок, при чому кожна комірка може містити один символ алфавіту даних. Таким чином, одиниці обсягу даних і пам’яті узгоджено. При цьому пам’ять може бути нескінченною. 3. Як виконавець алгоритму можуть виступати людина, різні технічні пристрої, наприклад робот або ЕОМ. У будь-якому випадку має бути досягнута визначена мета, інакше вся виконувана послідовність дій втрачає зміст. Однак навіть при виконанні цих вимог не всяка послідовність дій є алгоритмом. Для цього треба виконати кілька умов, що визначають властивості алгоритму: 1. Детермінованість визначення кроків алгоритму, тобто після кожного кроку або зазначається, який крок слід робити далі, або дається команда на зупинку, після чого робота алгоритму вважається закінченою. Ця властивість означає, що застосування алгоритму до тих самих даних має привести до одного і того самого результату. 2. Масовість алгоритм може бути використаний для розв’язан- ня цілого класу задач одного типу, наприклад квадратного рівняння з різними коефіцієнтами. 3. Результативність(скінченність, збіжність) виконання алгорит му має або закінчуватися результатом, або інформацією про те, чому не може бути одержаний результат, причому множина різних кроків, з яких складено алгоритм, є скінченною. Наприклад, після роз’язання квадратного рівняння дає значення його коренів або інформацію про їх відсутність при від’ємному дискримінанті. Проте перевірити результативність набагато важче, ніж вимоги, викладені вище. На відміну від них збіжність, як правило, не вдається встановити простим переглядом опису алгоритму; загального ж методу перевірки збіжності, придатного для будь-якого алгоритму і будь-яких даних, як буде показано далі, взагалі не існує. 4. Зрозумілість алгоритм має бути зрозумілим конкретному виконавцю, який повинен виконати кожну команду алгоритму у строгій відповідності призначенням. 5. Дискретність можливість розбиття алгоритму на скінченну кількість етапів, причому результати попереднього етапу є вихідними для наступного. Таким чином, кожен алгоритм будується з розрахунку на конкретного виконавця і відповідним чином подається. Існують різні способи опису алгоритмів(словесний, табличний, псевдокод, графічний). Алгоритм для ЕОМ найзручніше зображати графічно у вигляді схем. Схеми алгоритмів складаються з символів, що мають задане значення, короткого пояснювального тексту і сполучних ліній. Схема програми складається з: - символів процесу, які показують фактичні операції оброблення даних; - лінійних символів, що показують потік керування; - спеціальних символів, використовуваних для полегшення написання чи читання програми. Існують три основних типи процесів оброблення інформації: лінійний, розгалужений і циклічний. При лінійному процесі оброблення інформації здійснюється послідовно, одна дія за іншою, і кожен етап алгоритму виконується тільки один раз. При розгалужуваному процесі інформація обробляється по одному із двох можливих шляхів, тобто ті чи інші дії виконуються залежно від деякої умови. При циклічному процесі ті самі дії по обробленню інформації потрібно виконати багаторазово. Їм відповідають базові структури(конструкції) алгоритмів: проходження(лінійна структура), розгалуження(структура, що розгалужується) повторення(циклічна структура). Реальний алгоритм будь-якого ступеня складності можна задати комбінацією зазначених базових структур. Приклад зображено на малюнку 1. Такий граф, в якому вершинам відповідають кроки, а ребрам переходи між ними, називається схемою алгоритму. Його вершини можуть бути двох типів: вершини, з яких виходить одне ребро(їх називають операторами), і вершини, з яких виходять два ребра(їх називають логічними умовами, або предикатами). Крім того, існують єдиний оператор кінця, з якого не виходить жодного ребра, та єдиний оператор початку. Важливою особливістю схеми є те, що зв’язки, які вона описує, не залежать від того, чи є кроки елементарними або самостійними алгоритмами, як кажуть у програмуванні, блоками. Можливість розблокувати алгоритм добре відома у програмуванні й вона там широко використовується: великий алгоритм поділяється на блоки, які можна роздати для програмування різним особам. Для певного блока неважливо, яку будову мають інші блоки; для програмування блока досить знати, де знаходиться вся початкова інформація, яка форма її подання, що має робити блок і куди записати результат. Схеми не містять відомостей ні про дані, ні про пам’ять, ні про набір елементарних кроків, який використовується. Зокрема треба мати на увазі, що коли в схемі не має циклів, це не означає, що немає циклів в алгоритмі(вони можуть бути в якому-небуть неелементарному блоці). По суті схеми це не мова, а засіб, хоча дуже зручний для однієї мети опису детермінізму алгоритму. Корисно ввести одне уточнення: умови, тобто точки розгалуження, можуть бути не тільки двозначними, а й багатозначними; важливо, щоб правильною була лише одна з можливих відповідей(наприклад, оператор CASE в Паскалі). Виявляється, що будь-який логічний алгоритм можна досить простими методами звести до числового. Тому теорію числових алгоритмів можна вважати універсальним апаратом для дослідження всіх алгоритмічних проблем. Алгоритмічні моделі, що розглядаються в цьому розділі, претендують на право вважатися формалізацією поняття “алгоритм”. Це означає, що вони мають бути універсальними, тобто допускати опис будь-яких алгоритмів. Тому може виникнути природне заперечення підходу, який пропонується: чи не приведе вибір конкретних засобів до втрати загальності формалізації? Якщо мати на увазі основну мету при створені теорії алгоритмів універсальність і пов’язану з нею можливість говорити в межах якої-небудь моделі про властивості алгоритмів узагалі, то ця суперечність знімається так По-перше, доводиться звідність одних моделей до інших, тобто показується, що кожний алгоритм, описаний засобом однієї моделі, може бути описаний засобами іншої. По-друге, завдяки взаємній звідності моделей в теорії алгоритмів удалося виробити інваріантну відносно моделей систему понять, що дає змогу говорити про властивості алгоритмів незалежно від того, яку формалізацію алгоритму вибрано. Ця система понять ґрунтується на понятті обчислювальної функції, тобто функції, для обчислення якої існує алгоритм. Однак хоча загальність формалізації у конкретній моделі не втрачається, різний вибір початкових засобів приводить до моделей різного типу. Можна виділити три основних типи універсальних алгоритмічних моделей, які різняться початковими евристичними міркуваннями щодо того, що таке алгоритм. Перший тип зв’язує поняття алгоритму з найтрадиційнішими поняттями математики обчисленнями та числовими функціями. Найбільш розвинена й вивчена модель цього типу рекурсивні функції є історично першою формалізацією поняття алгоритму. Другий тип грунтується на уявлені про алгоритм як про деякий детермінований пристрій, здатний виконувати в кожний окремий момент лише дуже примітивні операції. Таке уявлення не залишає сумнівів в однозначності алгоритму й елементарності його кроків. Крім того, евристика цих моделей близька до ЕОМ, а отже, до інженерної індустрії. Основною теоретичною моделлю цього типу є машина Тюрінга. Робота машини відбувається в дискретному часі. На кожному кроці кареткою(за різними джерелами головкою або пристроєм звернення до стрічки) розглядається єдина комірка, а символ , який зчитується, замінюється іншим (i=j означає, що символ не змінюється) залежно від стану машини у заданий тактовий момент із множини її можливих станів. Крім того, виробляється наступний стан машини, і команда, яка керує переміщенням по стрічці, підготовлює чергову комірку для розгляду на наступному кроці. Таких команд у МТ три: R розглядати сусідню праворуч комірку; L розглядати сусідню ліворуч комірку та E продовжувати розглядати колишню комірку. Очевидно, що є істотним, чи рухається каретка вздовж стрічки, чи каретка є нерухомою, а рухається кожного разу на один крок саме стрічка Нехай МТ може знаходитися тільки у скінченому числі різних . внутрішніх станів і в будь-який момент часу чергова операція є функцією поточного внутрішнього стану машини та скінченого виразу, зафіксованого на стрічці. Відповідно до наведеного вище означення, можна формально визначити МТ в такий спосіб: Q (t+1)=(Q(t), A(t)) ; R(t+1)=(Q(t), A(t)) ; D(t+1)=(Q(t) , A(t)), Де , , деякі функції, що пов’язують попередній стан і попередній вихідний(який розглядається) символ. Функція визначає зміну стану, а функціявихідне значення записує в комірку, що розглядається: операція запису може містити вилучення символу, який знаходився раніше в комірці. Функція просто повідомляє, куди саме рухається стрічка. Описувана машина є скінченною, але її можна вважати актуально нескінченною у тому розумінні, що після досягнення будь-якго кінця стрічки завжди може бути додана нова комірка. При цьому, звичайно, у будь-який конкретний момент часу довжина стрічки залишається скінченною. Формальний математичний опис МТ дано у працях А. М. Тюрінга, Е. Л. Поста, С. К. Клині [7], Дейвіса, Арбиба [11] та М. Мін- ського [4]. Використовувані в цих працях різні системи позначень еквівалентні одна одній. Повний стан машини, за яким однозначно можна визначити її подальшу поведінку, визначається внутрішнім станом машини, станом стрічки(тобто словом, записаним на ній) та положенням каретки на стрічці. Перед початком роботи на стрічку наносять початкове слово і задають початкові умови, тобто зазначать першу комірку, яка розглядається, та початковий стан. Після пуску машини процес перетворення інформації відбувається автоматично. Постає питання про функції, для яких існує МТ, що їх обчислює. Щодо МТ можна сказати, що ця функція визначається поведінкою машини. Аргумент з’являється на стрічці до початку обчислення, а значення функції для цього аргументу те, яке залишається на стрічці, коли обчислення закінчено. Скористуємось спеціальним командуванням натуральних чисел в алфавіті, що складається з одного символу одиниці: кожне натуральне число n подається (n +1) символом 1, тобто числа 0, 1, 2,....кодуємо словами 1, 11, 111,... . Універсальна машина Тьюрінга Суттєвий факт, який було доведено за допомогою МТ, це те, що існує така МТ, яка за певними початковими значеннями обчислює будь-яку задану функцію, що є обчислюваною за Тюрінгом. Як зазначено вище, систему команд для МТ можна інтерпретувати також як опис роботи конкретного механізму і як програму, тобто сукупність розпоряджень, які однозначно приводять до результату. Розбираючи приклади, читач мимоволі вибирає другу інтерпретацію, виступаючи в ролі механізму, який здатний відтворити роботу будь-якої МТ. Упевненість у тому, що користувачі все це будуть робити однаково(якщо не нароблять помилок, що, до речі, передбачається при роботі МТ), це, по суті, упевненість в існуванні алгоритму відтворення роботи МТ за заданою програмою, тобто системою команд. Справді, словесний опис такого алгоритму дати не важко. Як уже зазначалося у питанні основні означення, словесний опис алгоритму може бути неточним і потребувати формалізації. Оскільки як такою формалізацією поняття алгоритму розглядається МТ, природно поставити задачу побудови такої МТ, яка реалізує описаний алгоритм відтворення. Для МТ, що обчислює функцію однієї змінної, формулювання цієї задачі таке: побудувати МТ U, яка обчислює функцію двох змінних, причому U ( , a)= T(a) для якої-небуть машини Т із системою команд , якщо Т(а) визначено(тобто машина U(,а) зупиняється, якщо зупиняється машина Т при початкових даних а, і машина U(, а) не зупиняється, якщо не зупиняється машина Т(а). Будь-яку машину U, що має цю властивість, будемо називати універсальною МТ. Неважко узагальнити це формулювання на будь-яке число змінних. Проблема зупину Серед загальних вимог до алгоритмів згадувалася вимога результативності. Най кардинальнішим формулюванням тут була б вимога, щоб за будь-яким алгоритмом А і даними а можна було б визначити, чи приведе робота А за початкових даних а до результату, чи ні. Іншими словами, треба побудувати алгоритм В такий, що В(А, а)=І, якщо А(а) дає результат, та В(А, а)=Х, якщо(а) не дає результату. З урахуванням тези Тюрінга цю задачу можна сформулювати як задачу про побудову МТ: побудувати машинутаку, що для будь-якої МТ Т і будь-яких початкових даних для машини(, а)= І, якщо машина Т (а) зупиняється, та (, а)=Х, якщо вона не зупиняється. Ця задача називається проблемою зупину. Її формулювання трохи нагадує задачу про побудову універсальної машини і, зокрема, також передбачає вибір відповідного кодування та а в алфавіті машини . Проте у цьому випадку ніяке кодування не приводить до успіху. Теорема. Не існує МТ , яка вирішує проблему зупину для довільної машини Тюрінга Т. Теза Тюрінга. Зв’язок рекурсивних функцій з машинами Тюрінга А. Тюрінг запропонував гіпотезу, що формулюється так: “Класи обчислюваних й обчислювальних за Тюрінгом функцій збігаються”. Довести тезу Тюрінга, неможливо, оскільки саме поняття алгоритму(або ефективної процедури) є неточним. Це не теорема і не постулат математичної теорії, а твердження, яке показує теорію з тими об’єктами, для опису яких її створено. За своїм значенням теза Тюрінга нагадує гіпотези фізики про адекватність математичних моделей фізичним явищам та процесам. Підтвердженням тези Тюрінга є, по-перше, математична практика, а по-друге, той факт, що опис алгоритму у термінах будь-якої іншої відомої алгоритмічної моделі може бути зведений до його опису у вигляді МТ. Теза Тюрінга дає змогу, з одного боку, замінити неточні твердження про існування ефективних процедур (алгоритмів) точними твердженнями про існування МТ, а з іншого твердження про не існування МТ тлумачити як твердження про не існування алгоритмів узагалі. Проте не слід розуміти тезу Тюрінга у тому сенсі, що вся теорія алгоритмів може бути зведена до теорії МТ. Наприклад, у теорії складності алгоритмів (що швидко розвивається зараз і розглядає порівняльну складність алгоритмів за пам’яттю, кількістю дій тощо) результати, правильні в межах однієї алгоритмічної моделі(скажімо, про кількість дій, потрібних для обчислення функції), можуть виявитися неправильними в іншій моделі. Із зіставлення цих двох тез випливає таке твердження: функція обчислюється МТ тоді й тільки тоді, коли вона є частково-рекурсивною. Це твердження про еквівалентність двох алгоритмічних моделей (на відміну від тез) є точним математичним твердженням і потребує доведення. Теорема. Усяка частково-рекурсивна функція є обчислюваною на МТ. План доведення зрозумілий: спочатку доводиться, що найпростіші функції, які складають повну систему, є обчислюваними, а потім те, що оператори суперпозиції, примітивної рекурсії зберігають обчислюваність. Алгоритмічна нерозв’язуваність і машини Тюрінга Алгоритмічна проблема це проблема, що зводиться до відшукання загального методу(алгоритму) для розв’язання всіх задач деякого класу. З уточненням поняття алгоритму за допомогою МТ з’явилась ще одна можливість установлювати наявність алгоритмічно нероз’язуваних проблем, тобто проблем, для яких шуканий алгоритм відсутній. Теорема. Проблема самозастосування є алгоритмічно нерозв’язуваною. Доведення проведемо від супротивного. Припустимо, що шукана машина М існує. Тоді можна побудувати машину N , ЯКА: - є застосовною до всіх кодів номерів несамозастосовних машин; - не є застосовною до всіх кодів номерів само застосовних машин; Машина N є або самозастосовною, або несамозастосовною. Якщо вона самозастосовна, тобто застосовна до коду свого номера, то вона застосовна також до коду само застосовної машини, але тоді не виконується вимога. Якщо машина N несамозастосовна, тобто не застосовна до коду свого номера, то вона не застосовна до коду свого номера також до коду несамозастосовної машини, але тоді не виконується вимога. Ми прийшли до суперечності, ґрунтуючись на допущенні про існування машини М , що розв’язує проблему само застосування. Тому такої машини не існує, а це означає, що проблема само застосування є алгоритмічно нерозв’язуваною. Зазначимо, що не розв’язано загальну проблему: немає єдиного алгоритму, який роз’язував би проблему само застосування. Про це свідчать розглянуті вище приклади конкретних МТ, для яких такий алгоритм існує. Використовуючи результат теореми, можна довести нероз’язуваність інших алгоритмічних проблем. Теорема. Проблема застосування МТ, до початкового слова є алгоритмічно нероз’язуваною. У термінах МТ це означає, що не існує такої МТ, яка роз’язала б цю проблему в зазначеному вище сенсі. Отже, прийшли до суперечності, виходячи з допущення, що існує машина яка роз’язує проблему застосування. Тому такої машини не існує. Висновок В даній курсовій роботі, я розглянув основні поняття і властивості елементів теорії алгоритмів, розв’язування різних типів задач, проаналізував основні приклади й означення МТ, обчислюваність та деякі операції над машинами Тюрінга. Проаналізував функціонування універсальної МТ, і алгоритмічну нерозв’язуваність. Задача по теорії алгоритмів Задача Задано масив чисел і=1,n. Скласти блок-схему алгоритму знаходження кількості від’ємних елементів маси. Розв’язання задач по машинах Тюрінга Задача 1 Нехай (Х={0,1}, Q = {, , }, , (, P), де P має такий вигляд: 1 1 1 1 0 1 0 0 1 0 1 1 ( ( 1 ( 1 1, де в початковий момент головка оглядає перший символ слова р F(x) в стані . Неважко переконатися в тому, що ця машина Тюрінга реалізує алгоритм додавання одиниці до числа p, представленого в двійковій системі числення. Розглянемо деякі приклади. Нехай p = 100111; тоді маємо послідовність команд: 1 1 1 ( 0 0 1 ( 0 0 1 ( 1 1 1 ( ( 1 1 1 ( 1 1 1 ( ( ( -1 ( 1 0 -1 ( ( 1 0 -1 ( 1 0 -1 ( 0 1 -1 Внаслідок цього слово р = 100111 “переписалось” машиною в слово= 10000 = 100111 + 1 в двійковій системі числення. Задача 2 Нехай (Х = {0, 1}, Q = {, }, , (, P), де Р має такі команди: 0 0 -1 1 1 -1 ( 1 -1 Для цієї машини, як неважко переконатися, полягає в тому, що, почавши роботу з будь-якого непустого слова р, до цього слова приписується зліва символ 1. Машина при цьому не зупиняється. Отже, результат роботи машини не визначений, оскільки машина не застосовна до будь-якого непустого слова р ( F(x). Задача 3 Нехай (Х = {0, 1}, Q = {, }, , (, P), де P включає такі команди: ( ( 1 0 0 1 1 1 0 Дія цієї машини Тюрінга полягає в тому, що в слові р машина шукає символ 1( якщо він є) і, знайшовши його, зупиняється. Якщо слово р є записом числа в двійковій системі числення, то машина зупиняється, якщо це число не дорівнює нулю. Список використаних літературних джерел 1. Міхайленко В.М., Федоренко Н.Д., Демченко В.В. Дискретна математика: Підручник. – К., Вид-во Європ. ун-ту, 2003. – 319с. – Бібліогр.: с. 318. 2. Бардачов Ю. М. та ін. Дискретна математика: Підручник / Ю. М. Бардачов, Н. А. Соколова, В. Є. Ходаков; За ред. В. Є. Ходакові. К.: Вища шк.., 2002. 287 с.: іл..

Курсова робота Основи дискретної математики

x3mal1k

13.06.2013 20:06-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись