Может ли кто-нибудь объяснить правило 110 самым простым способом?

Ответ 1

Я буду разбираться: я не думаю, что вы ищете более подробную информацию о доказательстве, которое уже довольно сложно в статье, хотя в нем явно отсутствуют многие подробности.

В цитате из статьи которую вы цитируете: "В элементарном клеточном автомате одномерный шаблон 0 и 1 развивается в соответствии с простым набором правил. Независимо от того, будет ли точка в шаблоне равна 0 или 1 в новом поколении по ее текущему значению, а также по отношению к ее двум соседям. Автомат правила 110 имеет следующий набор правил..." (см. таблица википедии, которая следует)

Начальная точка, которую вы можете просмотреть в качестве данных, но которая может быть взята в качестве представления кода (представляющая код как данные, необходима для любого доказательства полноты Тьюринга, что восходит к исходным результатам Тьюринга), последовательность 0 и 1, часто, но не обязательно, окруженная с обеих сторон клетками, содержащими только 0. Правило 110 показывает, как эта последовательность эволюционирует. Например, если в одной строке есть шаблон из 3 1, средний 1 будет "умирать" (превратиться в 0) в следующую строку. То, что происходит с его двумя соседями, зависит от того, как шаблон распространяется за их пределы. Треугольные диаграммы, которые вы видите, представляют собой графическое представление эволюции автомата из исходного состояния, кодирование 1 как черного и 0 как белого цвета и представляющее эволюцию сверху вниз. Исходное состояние часто очень короткое, чтобы показать, как очень сложные шаблоны могут эволюционировать из простых начальных состояний.

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

Чтобы правильно понять доказательства, вам нужно будет понять, как данные (а затем и код) закодированы в стартовом шаблоне, и также похоже, что знакомство с системами циклических тегов очень поможет. Я не человек, чтобы объяснить это.

Хотя может показаться труднее понять ситуацию с двумерным клеточным автоматом, таким как Conway "Игра жизни" , мне показалось поучительным играть с эту игру, изучая "планеры", "планерные пушки" и "штурмовые поезда" и другие забавные конструкции. (Подушечный поезд строит планерные пушки, а планер стреляет планами). Они могут быть использованы для установления полноты Turing для этого автомата.

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

Ответ 2

Моя попытка краткого объяснения непрофессионалов:

• Правило 110 является элементарным клеточным автоматом: правилом для преобразования конечного шаблона 1 и 0 в другой шаблон 1 и 0.
• Когда правило 110 итеративно применяется к некоторым входным битовым последовательностям, шаблоны появляются в зависимости от подпоследовательности, найденной во входных битах. Учитывая достаточно итераций, может случиться следующее:
  • Оригинальная подпоследовательность отображается в том же месте, что и на исходном входе.
  • Оригинальная подпоследовательность сохраняется, но "перемещается" в другое место в битовом поле.
  • Две подпоследовательности, движущиеся друг к другу, взаимодействуют и "проходят" друг друга.
  • Две подпоследовательности объединяются для создания новой подпоследовательности.
• Различные подпоследовательности могут иметь символическое значение, например "1", "0", "тактовый импульс" или "производственное правило", которые соответствуют элементам циклической системы тегов.
• Со многими итерациями правила 110 на тщательно сконструированном входном битовом поле взаимодействие подпоследовательностей имитирует поведение системы циклических тегов.
• Система циклических тегов может использоваться для моделирования универсальной машины Тьюринга. Таким образом, система циклических тегов завершается Тьюрингом.
• Так как правило 110 может имитировать систему циклических тегов, оно также завершено Тьюрингом.

Ответ 3

В 1970 году Джон Конвей изобрел "Игра жизни" .

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

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

С тех пор было обнаружено, что Game of Life удивительно сложна - она ​​может генерировать множество очень сложных моделей, которые продолжают развиваться. Кроме того, было показано, что это Turing-complete, то есть вы можете кодировать произвольно сложные алгоритмы, используя комбинацию стартовых ячеек в качестве программы, и конечную комбинацию в результате. Тем не менее, потребовалось несколько лет, чтобы найти способы генерации сложных форм, таких как планеры или оружие.

Теперь вернемся к правилу 110. Проще говоря, правило 110 является одномерной вариацией игры жизни.

110 - это просто представление десятичной цифры двоичной строки 01101110, которая является короткой формой системы правил того, как текущее поколение ячеек (бит) будет be переводится в следующий, подобно Системе правил Жизни Жизни, умирающей от одиночества или переполненности и рождающейся из ровно трех соседей.

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

Ответ 4

Реализация в python:

(Будьте осторожны: настоящие программисты на python убьют вас за это)

import time

seed = raw_input("Feed me a string! (At least 3 characters long please)\n>")

lastline = '>'
iterator = 0

while (iterator<len(seed)):
    temp = (ord(seed[iterator]))%2
    if (temp == 1):
        lastline += '#'
    else:
        lastline += ' '
    iterator += 1

stop = 0
while (stop != 1): #Keep printing as long as CTRL-C isn't pressed
    #dummy = raw_input(lastline)
    print lastline
    iterator = 0
    nextline = '>'


    while (iterator<len(seed)):    #Convert entire string

        if (len(seed) < 3): # if wrong
            print "You had ONE JOB!"
            stop = 1

        elif (iterator == 0): # if at start
            if (lastline[1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        elif (iterator+1 == len(seed)): # if at end
            if (lastline[iterator+1] == ' '):
                nextline += ' '
            else:
                nextline += '#'

        else: #if in middle
            if (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #111
                nextline += ' '
            elif (lastline[iterator] == '#' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #110
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #101
                nextline += '#'
            elif (lastline[iterator] == '#' and lastline[iterator+1] == ' ' and lastline[iterator+2] == ' '): #100
                nextline += ' '
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == '#'): #011
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == '#' and lastline[iterator+2] == ' '): #010
                nextline += '#'
            elif (lastline[iterator] == ' ' and lastline[iterator+1] == ' ' and lastline[iterator+2] == '#'): #001
                nextline += '#'
            else: # (lastline[iterator-1] == ' ' and lastline[iterator] == ' ' and lastline[iterator+1] == ' '): #000
                nextline += ' '

        iterator += 1

    lastline = nextline
    time.sleep(0.02)