Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

Реферат

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

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

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

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

СОДЕРЖАНИЕ

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

<html>

<head>

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

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 true;

}

function tmStart() {

var ids = ["btnStep", "btnStart", "btnSetState", "btnSetConfig", "btnShowNextCommand"];

for(var i = 0; i < ids.length; i++)

document.getElementById(ids[i]).disabled = true;

document.getElementById("btnStop").disabled = false;

flTMDoStop = false;

tmShowNextCommand();

window.setTimeout(tmRepeatStep, ctlSpeed.value);

}

function tmRepeatStep() {

if(!flTMDoStop && tmStep()) {

tmShowNextCommand();

window.setTimeout(tmRepeatStep, ctlSpeed.value);

return;

}

document.getElementById("btnStop").disabled = true;

var ids = ["btnStep", "btnStart", "btnSetState", "btnSetConfig", "btnShowNextCommand"];

for(var i = ids.length; i--; )

document.getElementById(ids[i]).disabled = false;

}

function tmStop() {

flTMDoStop = true;

}

function tmSetAlphabet() {

tmClearErrors();

var alphabet = {};

alphabet['B'] = 'B';

var ids = (chkDigitIds + " " + chkAlphaIds + " " + chkSymbolIds).split(" ");

var smbs = (smbDigit + smbAlpha + smbSymbol);

for(var i = 0; i < ids.length; i++)

if(document.getElementById("symbol" + ids[i]).checked)

alphabet[smbs.charAt(i)] = smbs.charAt(i);

for(var i = 0; i < nExtraSymbolNumber; i++) {

var smb = document.getElementById("extraSymbol" + i).value;

if(!smb)

continue;

if(smb in alphabet)

return tmCompileError("Невозможно включить символ '" + smb +

"' в алфавит дважды");

if(smb.length != 1)

return tmCompileError("Невозможно включить в алфавит " + smb.length + "-буквенное слово '" + smb + "'");

alphabet[smb] = smb;

}

setTMAlphabet = alphabet;

return true;

}

function tmSetStates() {

tmClearErrors();

var states = {};

states['STOP'] = 'STOP';

var ids = chkStateIds.split(" ");

for(var i = 0; i < ids.length; i++)

if(document.getElementById("state" + ids[i]).checked)

states[stState[i]] = stState[i];

for(var i = 0; i < nExtraStateNumber; i++) {

var st = document.getElementById("extraState" + i).value;

if(!st)

continue;

if(st in states)

return tmCompileError("Невозможно включить состояние '" + st +

"' в множество состояний машины Тьюринга дважды");

// if(!st.match(/^[a-zA-Z0-9][a-zA-GI-KM-QS-Z0-9\_\^\*]*$/))

if(!st.match(/^[a-zA-Z0-9][^\s\-\>]*$/))

return tmCompileError("Некорректное имя для состояния: '" + st + "'");

states[st] = st;

}

setTMStates = states;

return true;

}

function tmAddStateInput(trParent, tdBefore) {

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

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

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

input.setAttribute("id", "extraState" + nExtraStateNumber++);

input.setAttribute("class", "extraState");

td.appendChild(input);

if(tdBefore)

td = trParent.insertBefore(td, tdBefore);

else

td = trParent.appendChild(td);

td.firstChild.className = "extraState";

return td;

}

function tmMoreStates() {

var tdMoreStates = document.getElementById("tdMoreStates");

var parent = tdMoreStates.parentNode;

var colsNumber = Math.ceil(nExtraStateNumber / 10) + 4;

var percentWidth = Math.floor(100 / colsNumber);

for(var td = parent.firstChild; td != tdMoreStates; td = td.nextSibling)

if(td.nodeName.toLowerCase() == "td")

td.setAttribute("width", percentWidth + "%");

tdMoreStates.setAttribute("width", 100 - colsNumber * percentWidth + "%");

var tdStateInput = tmAddStateInput(parent, tdMoreStates);

tdStateInput.setAttribute("width", percentWidth + "%");

for(var tr = parent.nextSibling; tr; tr = tr.nextSibling)

if(tr.nodeName.toLowerCase() == "tr")

var td = tmAddStateInput(tr);

}

function tmShowNextCommand() {

tmClearNextCommand();

var prefix = "" + tmGetCellValue(idxTMCurrentCell) + strTMCurrentState;

if(!setTMProgram || !(prefix in setTMProgram))

return;

var cmd = setTMProgram[prefix];

var txt = prefix + "->" + cmd.smbTo + cmd.stTo + cmd.mvTo;

var tn = document.createTextNode(txt);

ctlNextCommand.appendChild(tn);

}

function tmClearNextCommand() {

while(ctlNextCommand.childNodes.length)

ctlNextCommand.removeChild(ctlNextCommand.lastChild);

}

function btnShowNextCommand_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text))

tmShowNextCommand();

}

function btnStep_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text) && tmStep())

tmShowNextCommand();

}

function btnStart_click() {

tmClearNextCommand();

var text = ctlProgram.value;

if(!(tmSetAlphabet() && tmSetStates()))

return;

if(!tmSetState(strTMCurrentState))

return;

if(tmCompile(text))

tmStart();

}

function btnStop_click() {

tmStop();

}

function btnSetConfig_click() {

tmClearNextCommand();

var strConfig = ctlConfig.value;

if(tmSetAlphabet() && tmSetConfig(strConfig))

tmShowNextCommand();

}

function btnSetState_click() {

tmClearNextCommand();

var strState = ctlNewState.value;

if(tmSetStates() && tmSetState(strState))

tmShowNextCommand();

}

function ctlTape_click(n) {

if(flTMDoStop) {

tmFocusCell(n);

tmShowNextCommand();

}

function chkAllDigit_click(checked) {

var ids = chkDigitIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

function chkAllAlpha_click(checked) {

var ids = chkAlphaIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

function chkAllSymbol_click(checked) {

var ids = chkSymbolIds.split(" ");

for(var i = 0; i < ids.length; i++)

document.getElementById("symbol" + ids[i]).checked = checked;

}

</script>

<h1> Следующая команда </h1>

</div>

<h1> Текущее состояние </h1>

</div>

</table>

</div>

<input type="button"

id="btnShowNextCommand"

value="Показать следующую команду"

onclick="btnShowNextCommand_click()"/>

<input type="button"

id="btnStep"

value="Шаг"

onclick="btnStep_click()"/>

<input type="button"

value="Старт"

id="btnStart"

onclick="btnStart_click()"/>

Скорость

<option value="0"/>Мгновенно

<option value="50"/>Очень быстро

<option value="200"/>Быстро

<option value="500" selected="true"/>Неспешно

<option value="1000"/>Медленно

<option value="5000"/>Очень медленно

</select>

<input type="button"

value="Стоп"

id="btnStop"

disabled="true"

onclick="btnStop_click()"/>

<table width="50%"

class="definitions"

cellpadding="4">

<tr>

<h2>Состояние</h2>

<input type="textbox"

id="newState"

value="q1"/><br/>

<input type="button"

value="Установить"

id="btnSetState"

onclick="btnSetState_click()"/>

</td>

<td colspan="2"

width="50%">

<h2>Конфигурация</h2>

<input type="textbox"

id="config"

value="01000"/>

<br/>

<input type="button"

value="Установить"

id="btnSetConfig"

onclick="btnSetConfig_click()"/>

</td>

<h2>Множество состояний</h2>

<table width="50%"

class="states">

<tr>

<td width="25%"><input type="checkbox"

checked="true" disabled="true"/>STOP</td>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

<h2>Алфавит</h2>

<table

width="50%"

class="alphabet">

<tr>

<td width="33%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allDigit"

onclick="chkAllDigit_click(this.checked)"/>

Цифры

</td>

<td width="33%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allAlpha"

onclick="chkAllAlpha_click(this.checked)"/>

Буквы

</td>

<td width="34%"

style="font-family: sans-serif;"

colspan="2">

<input type="checkbox"

id="allSymbol"

onclick="chkAllSymbol_click(this.checked)"/>

Символы

</td>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

<tr>

</tr>

</table>

</td>

<h2>Команды</h2>

<textarea

id="program"

wrap="off">

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

1q1->1q1R

0q1->0q2R

1q2->1q1R

Bq1->BSTOP

Bq2->BSTOP

</textarea>

</td>

</tr>

</table>

<br>

</div>

</div>

<body>

</html>

</font>

4 ПРОТОКОЛЫ РАБОТЫ МАШИНЫ ТЬЮРИНГА

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

1q1->1q1R

0q1->0q2R

1q2->1q1R

Bq1->BSTOP

Bq2->BSTOP

ВЫВОДЫ

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

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

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

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

Машина Тьюринга. 3 📙 Курсовая → 🆔 121588