Машина Тьюринга
Автор работы: Пользователь скрыл имя, 09 Июня 2014 в 20:42, курсовая работа
Краткое описание
Устройство машины Тьюринга чрезвычайно просто, однако на ней можно выполнить практически любую программу. Для выполнения всех этих действий предусмотрена специальная таблица правил, в которой прописано, что нужно делать при различных комбинациях текущих состояний и символов, прочитанных с ленты.
В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.
Вложенные файлы: 1 файл
Машина Тьюринга.docx
— 121.01 Кб (Скачать файл) 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 + "'");
}
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>