Как создать машину Тьюринга, которая принимает однозначное десятичное число от 0 до 9 и выводит куб - PullRequest
Новая
       10

Как создать машину Тьюринга, которая принимает однозначное десятичное число от 0 до 9 и выводит куб

3 голосов
/ 15 апреля 2010

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

f(x) = x^3, where x is a single digit between 0 - 9 inclusive.

Исходя из моего понимания, я должен преобразовать число в двоичное, но как мне найти куб числа в двоичном виде.

Также, как мне написать куб на ленте.

Пока я думаю, что должен создать диаграмму состояний, которая принимает двоичные версии 0-9, но что дальше?

1 Ответ

2 голосов
/ 15 апреля 2010

Я бы сделал это так:

  • Напишите копию номера слева от вашего текущего номера
  • Напишите еще одну копию слева от этого
  • Умножьте номер оригинала на первую копию, удалив копию
  • Умножьте результат на вторую копию, удалив

Вам нужно будет написать копию и умножить «подпрограмму» (используя состояния) и перейти к ней, задав правильные состояния. Но я думаю, что это должно быть выполнимо (если много работы). Но, вероятно, меньше работы, чем кодирование всех кубов от 0 до 9.

...