Qualcuno può spiegare la regola 110 nel modo più semplice possibile?

Question

Non riesco a spiegarmi che cosa the Wikipedia article o the answer here dire. Qualcuno può spiegare la regola 110 in termini semplici? Come garantisce la completezza di Turing?

Answer 1

Avrò un tentativo di elaborazione: non penso che tu stia cercando ulteriori dettagli della dimostrazione che è già abbastanza complessa nell'articolo, anche se chiaramente omette molti dettagli.

Per citare dal article you cite:. "In un automa cellulare elementare, un modello unidimensionale del evolve 0 e 1 di base a un semplice insieme di regole se un punto nel modello sarà 0 o 1 dipende in nuova generazione sul suo valore attuale, nonché di quello dei suoi due vicini.L'automa della regola 110 ha il seguente insieme di regole ... " (vedere lo wikipedia table che segue)

Il punto di partenza, che è possibile visualizzare come i dati, ma che possono essere presi come una rappresentazione di codice (che rappresenta il codice in quanto i dati sono necessari per qualsiasi prova di completezza di Turing, questo risale ai risultati originali di Turing), è una sequenza di 0 e 1, spesso, ma non necessari ly, circondato su entrambi i lati da celle contenenti solo 0. La regola 110 mostra come si evolve quella sequenza. Ad esempio, se c'è un modello di 3 1 in una riga, il middle 1 "muore" (diventa uno 0) nella riga successiva. Quello che succede ai suoi due vicini dipende da come il modello si estende oltre loro. I diagrammi triangolari che vedi sono una rappresentazione grafica dell'evoluzione dell'automa dallo stato originale, che codifica 1 come nero e 0 come bianco e rappresenta l'evoluzione dall'alto verso il basso. Lo stato iniziale è spesso molto breve per mostrare come modelli molto complessi possano evolvere da semplici stati iniziali.

Due caratteristiche insolite della prova di Turing completezza sono che, in primo luogo, sembra altamente improbabile che una tale regola molto semplice potrebbe fare tutto ciò che il linguaggio di programmazione preferito potrebbe fare, e in secondo luogo, il che rende il primo fatto un po 'meno sorprendente, è che la dimostrazione richiede uno sfondo a ripetizione infinitamente lungo su cui lavorare la sua magia. Non riesco a vedere nulla di fondamentalmente disonesto su questo però; non più che assumere un nastro bianco potenzialmente infinito o semi-infinito, come in origine Turing.

Per comprendere correttamente la dimostrazione, è necessario comprendere come i dati (e più tardi, il codice) sono codificati nello schema di partenza, e sembra anche che la familiarità con i sistemi di tag ciclici possa essere di grande aiuto. Non sono la persona per spiegarle.

Sebbene possa sembrare più difficile capire la situazione con un automa cellulare 2D, come Conway "Game of Life", ho trovato istruttivo giocare con quel gioco, studiando "alianti", "alianti" e "treni palla" e altre costruzioni divertenti. (Un treno palla costruisce cannoni a vela e un aliante spara alianti). Questi possono essere usati per stabilire la completezza di Turing anche per questo automa.

È inoltre possibile trovare il talk page informativo (non siete soli nel non cogliere il punto, vedere la voce che inizia "le immagini non fanno alcun senso per me ..").

Answer 2

Il mio tentativo di termini spiegazione di una succinta, del profano:

• Rule 110 è un automa cellulare elementare: una regola per trasformare un modello finito di 1 e 0 in un altro modello di 1 e 0.
• Quando la regola 110 viene applicata iterativamente su determinate sequenze di bit di input, i modelli emergono in base alle sequenze secondarie trovate nei bit di input. In caso di iterazioni sufficienti, può verificarsi quanto segue:
  • La sequenza secondaria originale viene visualizzata nella stessa posizione dell'input originale.
  • La sequenza secondaria originale viene mantenuta ma "sposta" in un'altra posizione nel campo bit.
  • Due sequenze secondarie che si spostano l'una verso l'altra interagiscono e si "passano" l'una con l'altra.
  • Due sottosequenze si combinano per creare una nuova sotto-sequenza.
• Diverse sotto-sequenze possono avere un significato simbolico come '1', '0', 'clock pulse' o 'regola di produzione' che corrispondono agli elementi di un sistema di tag ciclici.
• Con molte iterazioni della Regola 110 su un campo di bit di input costruito con cura, l'interazione delle sottosequenze simula il comportamento di un sistema di tag ciclici.
• Un sistema di etichette cicliche può essere utilizzato per simulare una macchina di Turing universale. Quindi un sistema di tag ciclico è completo di Turing.
• Poiché la regola 110 può simulare un sistema di tag ciclico, anche questo è completo di Turing.

Answer 3

Nel 1970 John Conway ha inventato Game of Life.

Da allora, penso che quasi tutti i programmatori abbiano provato a scrivere la sua implementazione - l'ho sicuramente fatto molto tempo fa, ed è stato molto divertente.

Questo gioco è in realtà cellular automaton, che imposta regole semplici tra generazioni di celle in un piano bidimensionale infinito. Ad esempio, se nella cella di generazione corrente ha meno di 2 vicini di casa (valore bit 1), allora dovrebbe morire nella prossima generazione di solitudine. Se ha più di 3 vicini di casa vivi, dovrebbe morire di sovraffollamento. Se vuota (valore bit 0, o dead) la cella ha esattamente 3 vicini, ne causerà la nascita (diventa 1).

Da allora, è stato rilevato che Game of Life è sorprendentemente complesso: può generare molti schemi molto complessi che continuano ad evolversi. Inoltre, è stato dimostrato che è completo di Turing, cioè, è possibile codificare algoritmi arbitrariamente complessi utilizzando la combinazione di celle iniziali come un programma e la combinazione finale come risultato. Tuttavia, ci sono voluti alcuni anni per scoprire come generare effettivamente forme complicate, come gliders or guns.

Ora torna a quale regola 110 è. In poche parole, la regola 110 è una variazione unidimensionale di Game of Life.

110 è solo una rappresentazione numero decimale di stringa binaria 01101110 che è breve sotto forma di sistema di regole di come attuale generazione di cellule (bit) saranno translated into next one, simile a Game of Life di sistema di regole di cellule che muoiono di solitudine o di sovraffollamento e essere nato per avere esattamente tre vicini.

Proprio come Game of Life, è stato dimostrato che la regola 110 è completa per Turing. È possibile codificare algoritmi arbitrariamente complessi utilizzando combinazioni di celle iniziali (bit) come il proprio programma e combinazione di bit finali come risultato.

Answer 4

Un'implementazione in Python:

(be si raccomanda: effettivi programmatori Python ti uccideranno per questo)

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)