Автор: Пользователь скрыл имя, 12 Июля 2013 в 00:49, курсовая работа
Теорія алгоритмів - дисципліна що вивчає як саме поняття алгоритму, так і поняття алгоритмічної розв'язності задач.
Перші, та найчисленніші застосування теорія алгоритмів мала в математичній логіці, адже вона виникла саме як розділ математичної логіки. Теорія алгоритмів є фундаментом програмування та інформатики.
Поштовхом до виникнення теорії алгоритмів, як окремого розділу математики, стала невдача в знаходженні алгоритмів розв'язку деяких масових проблем. Найвідомішими з них були проблема істинності для арифметичних формул, проблема істинності для формул числення предикатів першого порядку та десята проблема Гільберта про розв'язність діофантових рівнянь.
Умова задачі…………………………………………………………………………………..…2
Вступ…………………...……………………………………………………………………………3
Опис алгоритму………………………………………….………………………………….…4
Приклад………………….……………………………………………………………………..…7
Лістинг програми..………………………………………………………………………......8
Результат роботи програми…………………………………………….……………16
Висновок.……………………………………………………………………………………….17
Література………………………………………………………………..……………………18
tape += "^";
if (q == q_f && tape[head] == in) {
Ar = tape->ToCharArray();
Ar[head] = out;
q = q_l;
tape = "";
for (int i = 0; i < Ar->Length; ++i)
tape += Ar[i];
if (move == 'r' || move == 'R')
head++;
else if (move == 'l' || move == 'L')
head--;
if (in != out)
return tape;
else
return tape;
}
}
inline int TuringMachine::GetStatus()
{
return q;
}
inline String^ TuringMachine::GetTape()
{
return tape;
}
inline int TuringMachine::GetHead()
{
return head;
}
Результат роботи програми
Запустив програму:
Рис. 1. Результат роботи запущеного емулятора
Для прикладу, в поле вводу числа, ввів 30.
30 в шістнадцятковій системі це – 1B.
Рис. 2. Результат роботи емулятора на прикладі
Результат роботи програми збігається з переводом числа.
Висновок
Машина Тьюрінга складається з необмеженої в обидва боки стрічки, розділеної на гнізда, послідовно пронумеровані цілими числами, як позитивними, так і негативними.
У кожнім гнізді стрічки може стояти будь-який символ із заданого алфавіту, у якім виділений «порожній» символ — ознака того, що гніздо порожнє.
Машина має кінцеву безліч
Крім стрічки є головка
Програма — це таблиця, у якій у кожній клітці записана команда. Кожна клітка визначається двома параметрами — символом алфавіту й станом машини. Команда — ця вказівка, куди пересунути головку читання/запису з поточного стану, який символ записати в поточне гніздо й у який стан перейде машина.
Машина Тьюрінга — це модель комп'ютера.
Машина одержала ім'я математика А. Тьюрінга (Англія) і вирішує наступну проблему: якщо для рішення завдання можна побудувати машину Тьюрінга, вона алгоритмічно розв'язна.
Чи можна будь-який алгоритм представити у формі машини Тьюрінга? Відповідь на це питання дається у вигляді так званого тези Тьюрінга: усякий алгоритм представимо у формі машини Тьюрінга. Це теза тому, що його неможливо довести, тому що в ньому фігурують, з одного боку, інтуїтивне поняття «усякий алгоритм», а з іншого сторони — точне поняття «машина Тьюрінга».
Використана література