Машина Тьюринга
Автор работы: Пользователь скрыл имя, 09 Июня 2014 в 20:42, курсовая работа
Краткое описание
Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.
Вложенные файлы: 1 файл
Машина Тьюринга.docx
— 121.01 Кб (Скачать файл)<TD><INPUT id=stateQ13 type=checkbox>q13</TD>
<TD><INPUT id=extraState3 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ4 type=checkbox>q4</TD>
<TD><INPUT id=stateQ14 type=checkbox>q14</TD>
<TD><INPUT id=extraState4 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ5 type=checkbox>q5</TD>
<TD><INPUT id=stateQ15 type=checkbox>q15</TD>
<TD><INPUT id=extraState5 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ6 type=checkbox>q6</TD>
<TD><INPUT id=stateQ16 type=checkbox>q16</TD>
<TD><INPUT id=extraState6 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ7 type=checkbox>q7</TD>
<TD><INPUT id=stateQ17 type=checkbox>q17</TD>
<TD><INPUT id=extraState7 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ8 type=checkbox>q8</TD>
<TD><INPUT id=stateQ18 type=checkbox>q18</TD>
<TD><INPUT id=extraState8 class=extraState type=textbox></TD></TR>
<TR>
<TD><INPUT id=stateQ9 type=checkbox>q9</TD>
<TD><INPUT id=stateQ19 type=checkbox>q19</TD>
<TD><INPUT id=extraState9 class=extraState
type=textbox></TD></TR></TBODY></TABLE></TD>
<TD>
<H2>Алфавит</H2>
<TABLE class=alphabet width="100%">
<TBODY>
<TR>
<TD style="FONT-FAMILY: sans-serif" width="33%" colSpan=2><INPUT
id=allDigit onclick=chkAllDigit_click(this.checked) type=checkbox>
Цифры </TD>
<TD style="FONT-FAMILY: sans-serif" width="33%" colSpan=2><INPUT
id=allAlpha onclick=chkAllAlpha_click(this.checked) type=checkbox>
Буквы </TD>
<TD style="FONT-FAMILY: sans-serif" width="34%" colSpan=2><INPUT
id=allSymbol onclick=chkAllSymbol_click(this.checked) type=checkbox>
Символы </TD></TR>
<TR>
<TD><INPUT id=symbol0 CHECKED type=checkbox>0</TD>
<TD><INPUT id=symbolA type=checkbox>a</TD>
<TD><INPUT id=symbolK type=checkbox>k</TD>
<TD><INPUT id=symbolU type=checkbox>u</TD>
<TD><INPUT disabled CHECKED type=checkbox>B</TD>
<TD><INPUT id=extraSymbol0 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol1 CHECKED type=checkbox>1</TD>
<TD><INPUT id=symbolB type=checkbox>b</TD>
<TD><INPUT id=symbolL type=checkbox>l</TD>
<TD><INPUT id=symbolV type=checkbox>v</TD>
<TD><INPUT id=symbolLess type=checkbox><</TD>
<TD><INPUT id=extraSymbol1 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol2 type=checkbox>2</TD>
<TD><INPUT id=symbolC type=checkbox>c</TD>
<TD><INPUT id=symbolM type=checkbox>m</TD>
<TD><INPUT id=symbolW type=checkbox>w</TD>
<TD><INPUT id=symbolGreater type=checkbox>></TD>
<TD><INPUT id=extraSymbol2 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol3 type=checkbox>3</TD>
<TD><INPUT id=symbolD type=checkbox>d</TD>
<TD><INPUT id=symbolN type=checkbox>n</TD>
<TD><INPUT id=symbolX type=checkbox>x</TD>
<TD><INPUT id=symbolEqual type=checkbox>=</TD>
<TD><INPUT id=extraSymbol3 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol4 type=checkbox>4</TD>
<TD><INPUT id=symbolE type=checkbox>e</TD>
<TD><INPUT id=symbolO type=checkbox>o</TD>
<TD><INPUT id=symbolY type=checkbox>y</TD>
<TD><INPUT id=symbolPlus type=checkbox>+</TD>
<TD><INPUT id=extraSymbol4 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol5 type=checkbox>5</TD>
<TD><INPUT id=symbolF type=checkbox>f</TD>
<TD><INPUT id=symbolP type=checkbox>p</TD>
<TD><INPUT id=symbolZ type=checkbox>z</TD>
<TD><INPUT id=symbolMinus type=checkbox>-</TD>
<TD><INPUT id=extraSymbol5 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol6 type=checkbox>6</TD>
<TD><INPUT id=symbolG type=checkbox>g</TD>
<TD><INPUT id=symbolQ type=checkbox>q</TD>
<TD><INPUT id=extraSymbol10 type=textbox></TD>
<TD><INPUT id=symbolStar type=checkbox>*</TD>
<TD><INPUT id=extraSymbol6 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol7 type=checkbox>7</TD>
<TD><INPUT id=symbolH type=checkbox>h</TD>
<TD><INPUT id=symbolR type=checkbox>r</TD>
<TD><INPUT id=extraSymbol11 type=textbox></TD>
<TD><INPUT id=symbolSlash type=checkbox>/</TD>
<TD><INPUT id=extraSymbol7 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol8 type=checkbox>8</TD>
<TD><INPUT id=symbolI type=checkbox>i</TD>
<TD><INPUT id=symbolS type=checkbox>s</TD>
<TD><INPUT id=extraSymbol12 type=textbox></TD>
<TD><INPUT id=symbolHat type=checkbox>^</TD>
<TD><INPUT id=extraSymbol8 type=textbox></TD></TR>
<TR>
<TD><INPUT id=symbol9 type=checkbox>9</TD>
<TD><INPUT id=symbolJ type=checkbox>j</TD>
<TD><INPUT id=symbolT type=checkbox>t</TD>
<TD><INPUT id=extraSymbol13 type=textbox></TD>
<TD><INPUT id=symbolPercent type=checkbox>%</TD>
<TD><INPUT
id=extraSymbol9 type=textbox></TD></TR></TBODY></TABLE></TD>
<TD width="100%">
<H2>Команды</H2><TEXTAREA id=program wrap=off>// Прибавление единицы
// к двоичному числу
1q1->1q1R
0q1->0q1R
Bq1->Bq2L
1q2->0q2L
0q2->1q3L
Bq2->1STOP
0q3->0q3L
1q3->1q3L
Bq3->BSTOPR</TEXTAREA> </TD></TR></TBODY></TABLE>
<DIV class=error-container><NOBR id=errorType></NOBR><BR><NOBR
id=errorMessage></NOBR></DIV>
<DIV class=copy>© Алексей Михайлов 2014</DIV></DIV></BODY></HTML>
Заключение
Теория сложности также классифицирует
и сложность самих проблем, а не только
сложность конкретных алгоритмов решения
проблемы. Теория рассматривает минимальное
время и объем памяти, необходимые для
решения самого трудного варианта проблемы
на теоретическом компьютере, известном
как машина Тьюринга. Машина Тьюринга
представляет собой конечный автомат
с бесконечной лентой памяти для чтения
записи и является реалистичной моделью
вычислений.
Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними:
P <= NP <= EXPTIME
Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно угадывая”, либо перебирая все предположения параллельно – и проверяет свое предположение за полиномиальное время.
Класс NP включает в себя класс P, поскольку любую задачу, решаемую за полиномиальное время на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной за полиномиальное время, просто этап предположения опускается.
Если все задачи класса NP решаются за полиномиальное время и на детерминированной машине, то P=NP. Тем не менее, никем не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.
Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.
Список литературы
- Рощин А.Г., Половов Р.М. Теория автоматов. Часть I. Тексты лекций - Москва: МГТУ ГА, 2001. - 76 с.
- Фалевич Б.Я. Теория алгоритмов. – М.: ИНФРА-М, 2006. – с.324.
- Фалина Н.М. Машина Тьюринга // Информатика. - №26. – 2005. – с.12-15