Wireworld

2 Wireworld-Dioden, die obere wird in Durchlass-, die untere in Sperrrichtung betrieben.

Wireworld ist ein Zellulärer Automat, der erstmals von Brian Silverman 1987 in seinem Programm Phantom Fish Tank verwendet wurde und später durch einen Artikel in der Kolumne Computer Recreations des Scientific American weitere Verbreitung fand. Wireworld eignet sich besonders für die Simulation elektronischer Logikelemente wie Gatter oder Flipflops. Trotz der Einfachheit seiner Regeln (s. u.) ist Wireworld Turing-vollständig, d. h. man kann damit sogar vollständige Computer erstellen (s. auch Weblink).

Regeln

Eine Wireworld-Zelle kann vier unterschiedliche Zustände einnehmen (die jeweils angegebene Farbe wird in den animierten Grafiken auf dieser Seite verwendet):

schwarz steht für leer
gelb steht für „elektrischer Leiter“
blau steht für „Elektronenkopf“
rot steht für „Elektronenende“

Die Zeit verläuft in diskreten Schritten, den sogenannten Generationen. Dabei bleibt eine leere Zelle grundsätzlich leer. Die übrigen Zellen verhalten sich beim Übergang von einer Generation zur nächsten wie folgt:

Aus einem Elektronenkopf wird ein Elektronenende.
Aus einem Elektronenende wird ein Leiter.
Aus einem Leiter wird ein Elektronenkopf, wenn genau ein oder zwei der benachbarten Zellen Elektronenköpfe sind. Als benachbart gelten dabei die sogenannten Moore-Nachbarn, das sind alle Zellen, die den Leiter umgeben, auch die nur diagonal angrenzenden.

Anwendungen

Wendet man diese Regeln auf folgende Anordnung von Zellen an, so bewegt sich das Elektron bei jedem Generationswechsel um eine Position nach rechts (= Leiter, # Elektronenende, @ Elektronenkopf):

Generation n       ====#@========

Generation n + 1   =====#@=======

Generation n + 2   ======#@======

Durch geeignete Ausbildung von Leiterverzweigungen und -kreuzungen können logische Schaltelemente vom einfachen Gatter bis zum komplexen Rechenwerk realisiert werden.

Datei:Wireworld XOR-gate.gif

Zwei Taktgeneratoren und ein Exklusiv-Oder-Gatter

Das Bild links zeigt die Implementierung zweier Taktgeber (linke Bildhälfte) und eines Exklusiv-Oder-Gatters (rechts). Die Taktgeneratoren sind als ringförmige Leiterbahnen ausgeführt, in denen jeweils zwei Elektronen in unterschiedlichen Abständen kreisen. An den Verzweigungen am rechten Rand der Ringe werden Kopien dieser Elektronen in die zu den Eingängen des Exklusiv-Oder-Gatters führenden Leiterbahnen emittiert. Die Taktgeber sind derart aufeinander abgestimmt, dass entweder jeweils ein einzelnes Elektron von oben oder unten in das Exklusiv-Oder-Gatter eintritt (es wird durchgelassen), oder zwei Elektronen gleichzeitig am Gatter eintreffen – sie „vernichten“ sich gegenseitig und am Gatter-Ausgang tritt kein Elektron aus. Damit ist eine XOR-Verknüpfung der an den Gatter-Eingängen eintretenden Elektronen realisiert.

Signale

In Wireworld gibt es verschiedene Codierungen zur Übertragung von Daten. Allen gemein ist, dass ein Gesamtsignal in Blöcke gleicher Länge aufgeteilt wird. Eine Codierung mit der Blocklänge n nennt man „n-Micron“- oder auch „n-Tick“-Codierung.

In den sogenannten Real-Codierungen wird eine logische 0 durch einen leeren Block und eine 1 durch einen Block mit einem Elektron am Anfang repräsentiert. Die minimale Blocklänge beträgt dabei 3, da zwischen zwei Elektronen immer mindestens ein Feld Abstand sein muss. In den Complex-Codierungen wird eine 1 wie gehabt durch ein Elektron am Anfang des Blockes, eine 0 jedoch nicht durch kein, sondern durch ein um eine Generation verzögertes Elektron repräsentiert. Hier beträgt die minimale Blocklänge 4. Üblicherweise nutzt man

6-Micron-Real
4-Micron-Real
4-Micron-Complex
3-Micron-Real

Die Codierungen mit geringerer Blockgröße sind dabei schneller, benötigen aber unter Umständen aufwendigere Schaltungen.

Siehe auch

Conways Spiel des Lebens
Es existiert eine Wireworld-Implementierung von Langtons Ameise; sie ist in den Golly-Beispielpatterns enthalten.

Weblinks

[{{canonicalurl:Commons:Category:{{#if:|{{{1}}}|Wireworld}}|uselang=de}} Commons: {{#if:|{{{2}}}|{{#if:|{{{1}}}|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if:

   | {{#ifeq: {{#invoke:Str|left||9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

Implementierung eines vollständigen Computers mittels Wireworld
Zusammenstellung von 3-Tick- und 4-Tick-Schaltkreisen
<templatestyles src="Webarchiv/styles.css" />{{#if:20130604035805

      | {{#ifeq: 20130604035805 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20130604035805}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20130604035805}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Mit Wireworld implementierte Multiplizierer | {{#invoke:WLink|getEscapedTitle|Mit Wireworld implementierte Multiplizierer}} | {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20130604035805|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Mit Wireworld implementierte Multiplizierer
    | {{#if: {{#invoke:WLink|isBracketedLink|Mit Wireworld implementierte Multiplizierer}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.maa.org/editorial/mathgames/mathgames_05_24_04.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

Ein interaktives Applet zum Experimentieren mit Wireworld