машина Тьюринга Design

Question

Недавно я столкнулся со следующей проблемой:

Дайте схему машины Тьюринга для машины Тьюринга, которая на входе строку x ∈ {0, 1}∗ привалов (принимает) с его головы на левом конце ленты, содержащей строка x′ ∈ {0, 1}∗ на левом конце (и пустая в противном случае), где x '- последовательность преемника x в лексикографическом порядке; то есть следующую строку в последовательности ε, 0, 1, 00, 01, 10, 11, 000, . . ., в которой строки перечислены в порядке возрастания длины со связями, нарушенными их соответствующим целочисленным значением. (Кратко документируйте свою ТМ.)

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

Answer 1

Тьюринга машины

Во-первых, вы должны понимать, что машина Тьюринга, и машина Тьюринга, я предполагаю, что вы говорите о Universal Turing Machine. Это концептуальная машина, созданная Крестным отцом информатики Аланом Тьюрингом.

Машина построена из нескольких компонентов. Во-первых, бесконечная лента, содержащая входные данные. Что-то вроде ..

1-0-1-1-1-1-0-1-0-1-0 

Тогда набор правил ..

if 1 then 0 
if 0 then 1 

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

1-0-1-1 
^------------Current head. 

Тогда следующая итерация:

1-0-1-1 
    ^----------Current Head 

Эта машина фактически имитируя Поразрядные NOT функциональность. Вы также можете установить состояние в машине для извлечения, например:

if 1 then enter state 1 
if 0 then enter state 0 

Большая сделка право? Пример внезапно, теперь вы можете делать такие вещи, как:

1. if 1 and in state 1 output 1 and enter state 0 
2. if 1 and in state 0 output 0 and enter state 1 
3. if 0 and in state 0 output 1 and enter state 1 
4. if 0 and in state 1 output 0 and enter state 0 

И мы определяем состояние как состояние по умолчанию. В этом примере давайте назовем его state 0. Поэтому, когда машина запускается, она видит 1. Ну, я в state 0, и у меня только что есть 1, поэтому я собираюсь сделать номер правила 2. Выведите a 0 и введите state 1. Следующее число - 0. Ну, я в state 1, поэтому я звоню в номер правила 4. Смотрите, где это происходит? Добавляя состояния, вы действительно открываете, что можете сделать.

Теперь универсальная машина Тьюринга - это то, что известно как Turing Complete. Это означает, что он может вычислить любую вычислимую последовательность. В том числе, спецификация для вашего задания!

Вашего назначение

Итак, давайте посмотрим на вашем назначении в контексте машины Тьюринга.

Цель машины распечатать ..

0 1 00 01 11 000 001 011 111 

Итак, мы знаем, что нам нужно поддерживать состояние. Мы также знаем, что государству нужно углубляться и углубляться. Поэтому, если вы вводите пользователя в 000, нам нужно знать, что у нас есть три символа для вывода.

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