Машина тьюринга
Доброго времени суток!
Пожалуйста, помогите разобраться с решением задачи по МТ.
Прочитал теорию, тщательно поискав в гугле какие-нибудь решения примеров - ничего конкретного так и не удалось найти(
Задача:
Построить схему алгоритма Тьюринга, для вычисления функции:
(2*x1)*2 = z1
написать программу для вычисления заданной функции.
Теряюсь в том, что даже не пойму с чего здесь начинать. Почитав материал по тьюрингу - никаких реальных примеров на подобие поставленной мне задачи - не нашел. Пишу на C++.
Спасибо всем огромное, за любые подсказки/наводки по сути.
Пожалуйста, помогите разобраться с решением задачи по МТ.
Прочитал теорию, тщательно поискав в гугле какие-нибудь решения примеров - ничего конкретного так и не удалось найти(
Задача:
Построить схему алгоритма Тьюринга, для вычисления функции:
(2*x1)*2 = z1
написать программу для вычисления заданной функции.
Теряюсь в том, что даже не пойму с чего здесь начинать. Почитав материал по тьюрингу - никаких реальных примеров на подобие поставленной мне задачи - не нашел. Пишу на C++.
Спасибо всем огромное, за любые подсказки/наводки по сути.
В статье в википедии про машину Тьюринга приводится алгоритм умножения чисел в унарной системе счисления. Другие арифметические действия (в том числе и в других системах счисления) можно реализовать сходным образом.
turing-simulator-proc(var_x1)
var_state = "in_brackets";
while(1){
switch(var_state){
case "in_brackets":
var_x1 += var_x1;
var_state = "out_brackets";
break;
case "out_brackets":
var_x1 += var_x1;
var_state = "result";
break;
case "result":
var_z1 = var_x1;
var_state = "self-terminate";
break;
case "self-terminate":
0/0;
break;
}
}
в общем смысле как-то так ))))
var_state = "in_brackets";
while(1){
switch(var_state){
case "in_brackets":
var_x1 += var_x1;
var_state = "out_brackets";
break;
case "out_brackets":
var_x1 += var_x1;
var_state = "result";
break;
case "result":
var_z1 = var_x1;
var_state = "self-terminate";
break;
case "self-terminate":
0/0;
break;
}
}
в общем смысле как-то так ))))