Машина Тьюринга

Реферат

Отчет по курсовой работе содержит: 27 страниц, 3 рисунка, 0 таблиц, 8 источник, 2 приложение.

 

Объект исследования – машина Тьюринга.

1. Цель – сформировать формальное определение и написать программную реализацию машины Тьюринга, распознающей язык L = {wÎ{0, 1}^* │w не содержит 2-х идущих подряд нулей}
2. Результат – формальное определение, программная реализация машины Тьюринга, распознающей язык L = {wÎ{0, 1}^* │w не содержит 2-х идущих подряд нулей}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МАШИНА ТЬЮРИНГА, ВРЕМЕННАЯ СЛОЖНОСТЬ, АЛФАВИТ, ЛЕНТА, ЯЗЫК, РАСПОЗНАВАНИЕ, ПРОТОКОЛ, ПРИНАДЛЕЖНОСТЬ

 

СОДЕРЖАНИЕ

1. Ведение………………………………………………………………...4
2. ПОСТАНОВКА ЗАДАЧИ……………………………………….........6
3. ФОРМАЛЬНО ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА………..7
4. ПРОГРАММНАЯ МОДЕЛЬ МАШИНЫ ТЬЮРИНГА……….........8
5. ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА……...................22
6. ВЫВОД………………………………………………………………..23 
7. СПИСОК ЛИТЕРАТУРЫ…………………….………..………...... 25
8. Приложение А……………………………………………………....... 25
9. Приложение Б………………………………………………………....27

11.Экранные формы программы………………………… …………....27

 

 

 

ВВЕДЕНИЕ

 

Алгоритм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Машина Тьюринга (МТ) — математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому. В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство с конечным числом состояний.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

В управляющем устройстве содержится таблица переходов, которая представляет алгоритм, реализуемый данной Машиной Тьюринга. Каждое правило из таблицы предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния Машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, и недетерминированной в противном случае.

 

 1 ПОСТАНОВКА ЗАДАЧИ

 

1. Необходимо формально определить машину Тьюринга, распознающую язык L = {wÎ{0, 1}^* │w не содержит 2-х идущих подряд нулей}, проверить правильность составления машины Тьюринга на протоколах. Реализовать программную модель машины Тьюринга. Построить график временной сложности.

 

2. ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ МАШИНЫ ТЬЮРИНГА

 

// Не содержит 2-х подряд нулей

 

1q1->1q1R

0q1->0q2R

1q2->1q1R

Bq1->BSTOP

Bq2->BSTOP

K – множество состояний;

K={q₂, q₃, }.

S – входной алфавит; S={0, 1}.

Г – ленточный алфавит; Г = {0, 1}.

Q₁ – начальное состояние.

В – пустое множество.

STOP- состояние полной остановки машины;

 

 

 

3 ПРОГРАММНАЯ МОДЕЛЬ МАШИНЫ ТЬЮРИНГА

Содержание файла javascript.js

Файл содержит основные функции, реализующие работу программы.

 

<p style="line-height: 100%"><font size="6"><!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>

<head>

<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">

<title>Документ без названия</title>

<link href="style.css" rel="stylesheet" type="text/css">

<script type="text/javascript">

var ctlTape;

var ctlProgram;

var ctlErrorType;

var ctlErrorMessage;

var ctlConfig;

var ctlState;

var ctlNewState;

var ctlSpeed;

var ctlNextCommand;

var ctlTapeContainer;

var flTMDoStop = true;

// Поддержка алфавита

var chkDigitIds = "0 1 2 3 4 5 6 7 8 9";

var smbDigit = "0123456789";

var chkAlphaIds = "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z";

var smbAlpha = "abcdefghijklmnopqrstuvwxyz";

var chkSymbolIds = "Less Greater Equal Plus Minus Star Slash Hat Percent";

var smbSymbol = "<>=+-*/^%";

var nExtraSymbolNumber = 14;

var smbNBSP;

// Поддержка множества  состояний

var chkStateIds = "Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Q18 Q19";

var stState = ["q1", "q2", "q3", "q4", "q5", "q6", "q7", "q8", "q9",

"q10", "q11", "q12", "q13", "q14", "q15", "q16", "q17", "q18", "q19"];

var cellWidth = 30;

var nExtraStateNumber = 10;

var arTMTape = [];

var tapeShift = 100;

var setTMProgram;

var setTMAlphabet;

var setTMStates;

var strTMCurrentState;

var idxTMCurrentCell;

function init() {

ctlTape         = document.getElementById("tape");

ctlProgram      = document.getElementById("program");

ctlErrorType    = document.getElementById("errorType");

ctlErrorMessage = document.getElementById("errorMessage");

ctlConfig       = document.getElementById("config");

ctlState        = document.getElementById("state");

ctlNewState     = document.getElementById("newState");

ctlSpeed        = document.getElementById("speed");

ctlNextCommand  = document.getElementById("ctlNextCommand");

ctlTapeContainer  = document.getElementById("ctlTapeContainer");

smbNBSP = document.getElementById("ctlNBSP").firstChild.nodeValue;

for(var i = -tapeShift; i < tapeShift; i++) {

createCell(i);

}

tmClearTape();

}

function createCell(n) {

// var cell = document.createElement("div");

var cell = document.createElement("td");

var input = document.createElement("input");

input.setAttribute("type", "text");

input.setAttribute("size", 1);

cell.appendChild(input);

cell.setAttribute("tabindex", "1");

cell = ctlTape.appendChild(cell);

cell.firstChild.readOnly = true;

cell.tabIndex = 1;

cell.tapeIndex = n;

cell.onclick = function() { ctlTape_click(this.tapeIndex); };

// cell.setAttribute("style", "left: " + (30 * (n + tapeShift)) + "px");

return cell;

}

function tmFocusCell(n) {

if(!isNaN(idxTMCurrentCell)) {

var cell = ctlTape.childNodes[idxTMCurrentCell + tapeShift];

cell.className = cell.className.replace(/focused/, "")

.replace(/\s+/g, " ").replace(/^\s+/, "").replace(/\s+$/, "");

}

var cell = ctlTape.childNodes[n + tapeShift];

cell.className = "focused" + (cell.className ? " " + cell.className : "");

idxTMCurrentCell = n;

cell.firstChild.focus();

// if(ctlTapeContainer.doScroll) {

//   var th = Math.floor(600 / (tapeShift*2) * (n + tapeShift));

//   window.setTimeout(function() {

//   while(th--)

//     ctlTapeContainer.doScroll("scrollbarRight");

//   }, 50);

//   //alert(100 / (tapeShift*2) * (n + tapeShift));

// }

}

function tmSetCellValue(n, v) {

if(v == 'B')

v = '';

arTMTape[n + tapeShift] = v;

var cell = ctlTape.childNodes[n + tapeShift];

//while(cell.childNodes.length)

//  cell.removeChild(cell.lastChild);

//var txt = document.createTextNode(v || smbNBSP);

//cell.appendChild(txt);

cell.className = cell.className.replace(/blankSymbol/, "")

.replace(/\s+/g, " ").replace(/^\s+/, "").replace(/\s+$/, "");

if(v == '')

cell.className = "blankSymbol" + (cell.className ? " " + cell.className: "");

cell.firstChild.value = v;

}

function tmGetCellValue(n) {

var v = arTMTape[n + tapeShift];

return v == '' ? 'B' : v;

}

function tmClearErrors() {

while(ctlErrorType.childNodes.length)

ctlErrorType.removeChild(ctlErrorType.lastChild);

while(ctlErrorMessage.childNodes.length)

ctlErrorMessage.removeChild(ctlErrorMessage.lastChild);

}

function tmCompileError(strType, b, e) {

if(ctlProgram.setSelectionRange && typeof(ctlProgram.setSelectionRange) == "function" && b <= e) {

ctlProgram.select();

ctlProgram.setSelectionRange(b, e);

}

tmClearErrors();

var errT = document.createTextNode(strType);

ctlErrorType.appendChild(errT);

var strMessage = ctlProgram.value.substring(b, e);

var errM = document.createTextNode(strMessage);

ctlErrorMessage.appendChild(errM);

alert(strType);

}

function tmCompile(text) {

tmClearErrors();

function nextE(bb) {

var ee = text.substring(bb, text.length).indexOf("\n");

return ee == -1 ? text.length : bb + ee;

}

var arNewProgram = {};

for(var idxLine = 1, b = 0, e = nextE(b); b < text.length; b = e + 1, e = nextE(b), idxLine++ ) {

var line = text.substring(b, e);

line = line.replace(/\/\/.*$/, "");

line = line + " ";

// var arMatch = line.match(/^\s*(?:([^\s][a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*\-\>[^\s][a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*[LRH]?)\s+)*$/);

var arMatch = line.match(/^\s*(?:([^\s][a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*\-\>[^\s][a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*[LRH]?)\s+)*$/);

if(!arMatch)

return tmCompileError("Синтаксическая ошибка в " + idxLine + "-й строке", b, e);

for(var idxCmd = 1; idxCmd < arMatch.length; idxCmd++) {

var strCmd = arMatch[idxCmd];

if(!strCmd)

continue;

var parsedCommand = tmParseCommand(strCmd, idxLine);

if(!parsedCommand)

return tmCompileError("Непредвиденная ошибка в " + idxLine + "-й строке", b, e);

if("errorMessage" in parsedCommand)

return tmCompileError(parsedCommand.errorMessage, b, e);

var prefix = "" + parsedCommand.smbFrom + parsedCommand.stFrom;

if(prefix in arNewProgram)

return tmCompileError("Строка " + idxLine + ": Повторение команды " + strCmd + " для символа '"

+ parsedCommand.smbFrom + "' и состояния  " + parsedCommand.stFrom, b, e);

arNewProgram[prefix] = parsedCommand;

}

}

setTMProgram = arNewProgram;

return true;

}

function tmParseCommand(str, idxLine) {

// var arMatch = str.match(/(.)([a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*)\-\>(.)([a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*)([LRH]?)/);

var arMatch = str.match(/(.)([a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*)\-\>(.)([a-zA-Z0-9](?:[^\s\-\>]*[^\s\-\>LRH])*)([LRH]?)/);

if(!arMatch || arMatch.length != 6)

return {

errorMessage: "Строка " + idxLine + ": Непредвиденная ошибка в команде " + str

};

var smbFrom = arMatch[1];

var stFrom  = arMatch[2];

var smbTo   = arMatch[3];

var stTo    = arMatch[4];

var mvTo    = arMatch[5];

if(!(smbFrom in setTMAlphabet))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " символ '" + smbFrom + "' не входит в алвфавит Вашей машины Тьюринга"

};

if(!(stFrom in setTMStates))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " состояние '" + stFrom + "' не входит в множество состояний Вашей машины Тьюринга"

};

if(!(smbTo in setTMAlphabet))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " символ '" + smbTo + "' не входит в алвфавит Вашей машины Тьюринга"

};

if(!(stTo in setTMStates))

return {

errorMessage: "Строка " + idxLine + ": В команде " + str + " состояние '" + stTo + "' не входит в множество состояний Вашей машины Тьюринга"

};

if(!mvTo)

mvTo = 'H';

return {

smbFrom : smbFrom,

smbTo   : smbTo,

stFrom  : stFrom,

stTo    : stTo,

mvTo    : mvTo

};

}

function tmClearTape() {

for(var idxCell = -tapeShift; idxCell < tapeShift; idxCell++) {

tmSetCellValue(idxCell, "");

}

}

function tmSetConfig(strConfig) {

tmClearErrors();

for(var idxSymbol = 0; idxSymbol < strConfig.length; idxSymbol++)

if(!(strConfig.charAt(idxSymbol) in setTMAlphabet))

return tmCompileError("Символ '" + strConfig.charAt(idxSymbol) + "' не входит  в алфавит Вашей машины Тьюринга");

tmClearTape();

for(var idxSymbol = 0; idxSymbol < strConfig.length; idxSymbol++)

tmSetCellValue(idxSymbol, strConfig.charAt(idxSymbol));

tmFocusCell(strConfig.length + 1);

tmFocusCell(0);

}

function tmSetState(strState) {

tmClearErrors();

if(!strState)

return tmCompileError("Неопределенное  состояние машины Тьюринга");

if(!(strState in setTMStates))

return tmCompileError("Состояние  '" + strState + "' не входит в множество состояний Вашей машины Тьюринга");

while(ctlState.childNodes.length)

ctlState.removeChild(ctlState.lastChild);

tnState = document.createTextNode(strState);

ctlState.appendChild(tnState);

strTMCurrentState = strState;

return true;

}

function tmStep() {

tmClearErrors();

if(strTMCurrentState == "STOP") {

alert("Работа  машины Тьюринга успешно завершена");

return false;

}

if(!strTMCurrentState)

return tmCompileError("Не установлено  состояние машины Тьюринга");

if(!(strTMCurrentState in setTMStates))

return tmCompileError("Состояние  '" + strTMCurrentState + "' не входит в  множество состояний Вашей машины  Тьюринга");

if(isNaN(idxTMCurrentCell))

return tmCompileError("Не установлена  текущая ячейка машины Тьюринга");

var smbCurrent = tmGetCellValue(idxTMCurrentCell);

if(!smbCurrent)

smbCurrent = 'B';

if(!(smbCurrent in setTMAlphabet))

return tmCompileError("Символ '" + smbCurrent + "' не входит в алфавит Вашей машины Тьюринга");

 

var prefix = "" + smbCurrent + strTMCurrentState;

if(!setTMProgram)

return tmCompileError("Нет ни одной команды для выполнения");

if!(prefix in setTMProgram))

return tmCompileError("Нет команды  для символа '" + smbCurrent + "' и  состояния '" + strTMCurrentState + "'");

var cmd = setTMProgram[prefix];

if(!(cmd.smbTo in setTMAlphabet))

return tmCompileError("Символ '" + cmd.smbTo + "' не входит в алфавит Вашей машины Тьюринга\n" +

"При выполнении команды  для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

if(!(cmd.stTo in setTMStates))

return tmCompileError("Состояние '" + cmd.stTo + "' не входит в множество состояний Вашей машины Тьюринга\n" +

"При выполнении команды  для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

if(!(cmd.mvTo == 'L' || cmd.mvTo == 'R' || cmd.mvTo == 'H'))

return tmCompileError("Непредвиденная ошибка при выполнении перемещения в команде для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");

tmSetCellValue(idxTMCurrentCell, cmd.smbTo);

tmSetState(cmd.stTo);

switch(cmd.mvTo) {

case 'L':

tmFocusCell(idxTMCurrentCell - 1);

break;

case 'R':

tmFocusCell(idxTMCurrentCell + 1);

break;

case 'H':

break;

default:

return tmCompileError("Непредвиденная  ошибка при выполнении перемещения  в команде для символа '" + smbCurrent + "' и состояния '" + strTMCurrentState + "'");