In Erinnerung an Solomon Golomb (1932-2016): Autor eines Schieberegisters mit linearer Rückkopplung von maximaler Länge und Poliomino

Ursprünglicher Autor: Stephen Wolfram
  • Übersetzung

Übersetzung von Stephen Wolframs Beitrag " Solomon Golomb (1932–2016) ".
Vielen Dank an Polina Sologub für die Hilfe bei der Übersetzung und Vorbereitung der Veröffentlichung.




Inhalt


- Der am häufigsten verwendete mathematische Algorithmus in der Geschichte
- Wie ich Saul Golomb kennengelernt habe
- Geschichte von Solomon Golomb
- Schieberegister
- Hintergrund der Schieberegister
- Warum brauchen wir Sequenzen, die von Schieberegistern generiert werden?
" Nun, wo sind diese Register?"
- Zelluläre Automaten und Schieberegister mit nichtlinearem Feedback
- Poliomino
- Der Rest der Geschichte



Der am häufigsten verwendete mathematische Algorithmus in der Geschichte


Oktillion . Milliarden Milliarden Dies ist eine sehr grobe Schätzung, wie oft ein Mobiltelefon oder ein anderes Gerät unter Verwendung eines Schieberegisters mit linearer Rückkopplung maximaler Länge ein Bit erzeugt hat . Ich denke, dies ist der am häufigsten verwendete mathematische Algorithmus in der Geschichte. Der Autor ist Solomon Golomb , der am 1. Mai starb und den wir seit mehr als 35 Jahren kennen.

Die Grundlage des 1967 veröffentlichten Buches von Solomon Golomb „Sequences of Register Shift“ war sein Werk der 1950er Jahre. Und sein Inhalt lebt in jedem der modernen Kommunikationssysteme. Lesen Sie die Spezifikationen für 3G , LTE , Wi-Fi , Bluetooth oder sogar fürGPS - und Sie finden Verweise auf Polynome, die die von den Schieberegistern erzeugten Sequenzen definieren, mit denen diese Systeme die von ihnen gesendeten Daten codieren. Solomon Golomb ist der Mann, der diese Polynome geschaffen hat.

Darüber hinaus spielte er eine wichtige Rolle bei der Berechnung der Entfernung zur Venus mithilfe eines Radars sowie bei der Entwicklung der Bildcodierung für das Senden vom Mars. Er führte die Welt in das ein, was er Poliomino nannte (was später die Schöpfer von Tetris inspirierte - „Tetromino Tennis“). Er erstellte und löste unzählige mathematische Rätsel und Wortspiele. Vor ungefähr 20 Jahren fand ich heraus, dass er der Entdeckung meiner Lieblingsregel 30 für zellulare Automaten sehr nahe war 1959, als ich gerade geboren wurde.

Wie ich Saul Golomb kennengelernt habe


Ich habe fast alle Wissenschaftler und Mathematiker gelernt, die ich durch meine beruflichen Beziehungen kenne. Aber nicht Sola Golomba. Es war 1981, und ich, ein 21-jähriger Physiker (der in den Medien ein wenig bekannt wurde, weil ich bei der ersten Preisverleihung der jüngste Empfänger des MacArthur-Preises war), forschte am California Institute of Technology. Es klopfte an der Tür meines Büros und eine junge Frau überquerte bald die Schwelle. Dies war bereits ungewöhnlich, denn in jenen Tagen, in denen hochenergetische theoretische Physik betrieben wurde, gab es hoffnungslos wenige Frauen. Obwohl ich einige Jahre in Kalifornien gelebt habe, habe ich die Universität dennoch nicht verlassen und war daher schlecht vorbereitet auf den Anstieg der Energie in Südkalifornien, der in mein Büro eindrang. Die Frau stellte sich Astrid vor und sagte, sie besuche Oxford und kenne jemanden, mit dem ich im Kindergarten war. Sie erklärte, dass sie mit dem Sammeln von Informationen über interessante Menschen in der Region Pasadena betraut sei. Ich denke, sie hielt mich für einen schwierigen Fall, bestand aber dennoch auf einem Gespräch. Und einmal, als ich versuchte, etwas über meine Arbeit zu erzählen, sagte sie: "Du solltest dich mit meinem Vater treffen. Er ist ein alter Mann, aber sein Verstand ist immer noch messerscharf . "Und so kam es, dass Astrid Golomb, die älteste Tochter von Sol Golomb, mich ihm vorstellte.

Die Familie Golomb lebte in einem Haus in den Bergen in der Nähe von Pasadena Zwei Töchter: Astrid - etwas älter als ich, ein ehrgeiziges Hollywood-Mädchen und Beatrice - über mein Alter und meine wissenschaftliche Mentalität. Golomb-Schwestern hatten oft Partys - normalerweise zu Hause. Die Themen waren unterschiedlich: Dies war eine Gartenparty und ein Krocket mit Flamingos und Igel ("der Gewinner ist derjenige, dessen Kostüm am meisten ist Det fit Thema") oder eine Party im Stonehenge-Stil mit Anweisungen von Runen. Auf diesen Partys kreuzten sich junge und nicht so gute Leute, einschließlich verschiedener lokaler Koryphäen. Und für sie gab es, ein wenig beiseite, immer einen kleinen Mann mit einem großen Bart, ein bisschen wie der Elf und trug immer einen dunklen Mantel - Solomon Golomb selbst.

Ich lernte allmählich ein wenig über ihn. Dass er an der " Informationstheorie " beteiligt war. Dass er an der University of Southern California arbeitete . Dass er verschiedene vage hatte aber anscheinend auf hohem Niveau n avitelstvennye und andere Verbindungen. Ich habe von Schieberegistern gehört, aber fast wusste nichts über sie.

Im Herbst 1982 besuchte ich Bell Labsin New Jersey und hielt einen Vortrag über meine neuesten Erkenntnisse auf dem Gebiet der zellularen Automaten. Eines der Themen, die ich besprochen habe, war "additiv" (oder "linear"), zelluläre Automaten und deren Verhalten mit einer begrenzten Anzahl von Zellen . Immer wenn ein zellularer Automat eine begrenzte Anzahl von Zellen hat, wird sein Verhalten letztendlich unvermeidlich wiederholt ... Mit zunehmender Größe scheint jedoch die maximale Wiederholungsperiode, beispielsweise für Regel 90 für einen additiven zellularen Automaten, völlig zufällig zu seinBild: 1, 1, 3, 2, 7, 1, 7, 6, 31, 4, 63, ... Einige Tage vor der Rede bemerkte ich jedoch, dass diese Zeiträume einer Formel zu folgen scheinen, die von Primfaktoren oder Zahlen abhängt Zellen. Aber als ich das erwähnte, hob einer von denen, die weit saßen, seine Hand und fragte: „ Weißt du, ob das für n = 37 funktioniert ? "In meinen Experimenten habe ich mich nicht mit dieser Nummer befasst, also wusste ich es nicht. Aber warum hat mich jemand danach gefragt? Derjenige,

der mich fragte, hieß Andrew Odlyzhko - er war ein Theoretiker von Bell Labs. Ich fragte ihn:" Was Denken Sie, dass etwas Besonderes mit n = 37 verbunden sein könnte ? " Nun ", sagte er, "Ich denke, dass das, was Sie tun, mit der linearen Rückkopplungsverschiebungstheorie von Registern zusammenhängt ", und er schlug vor, dass ich mir Sol Golombs Buch anschaue." Oh ja ", sagte ich," ich kenne seine Töchter. . gibt es eine sehr. „Andrew richtig war elegant Theorie . Sola auf Polynome, analog zu der Theorie basieren entworfen Register mit linearer Rückkopplung Andrew zu verschieben , und ich schrieb der additiven zellulären Automaten auch jetzt die zitierten Artikel darüber (dies ist der seltene Fall ist , wenn die traditionelle Mathematik Methoden ermöglichen es, das Verhalten von Zellen zu beschreiben th Maschine). Ein paar Dinge waren , dass ich eine Nebenwirkung haben gelernt , was in Solomon Golomb beteiligt ist (wenn Sie sich erinnern, das war alles vor dem Internet).

Die Geschichte von Solomon Golomb


Solomon Golomb wurde 1932 in Baltimore, Maryland , geboren. Seine Familie stammte aus Litauen . Sein Großvater war Rabbiner, und sein noch sehr junger Vater zog in die USA und erhielt einen Master in Mathematik. Danach ging er in die mittelalterliche jüdische Philosophie und wurde auch Rabbiner. Sols Mutter stammte aus einer bekannten russischen Familie, die Stiefel für die Zarenarmee herstellte und dann die Bank leitete. Sol war in der Schule hervorragend und der stärkste in der Debatte. Inspiriert von seinem Vater interessierte er sich für Mathematik und veröffentlichte im Alter von 17 Jahren einen Artikel über Primzahlen. Nach dem Abitur schrieb er sich an der Johns Hopkins University einMathematik zu studieren, und fiel fast in die Quote für jüdische Studenten (so musste er versprechen, dass er nicht zur Medizin gehen würde, und dann absolvierte Sol, nachdem er seine Arbeitsbelastung verdoppelt hatte, 1951 die Universität in der Hälfte der üblichen Studienzeit).

Von dort ging er nach Harvard, um die Mathematikschule zu absolvieren. Zuvor arbeitete er jedoch im Sommer bei der Glenn L. Martin Company , einem 1912 gegründeten Luft- und Raumfahrtunternehmen, das in den 1920er Jahren nach Los Angeles im Baltikum zog und dort Verteidigungsunternehmen wurde, das schließlich zu Lockheed Martin wurde. In Harvard spezialisierte sich Sol auf die Zahlentheorie und insbesondere auf die Charakterisierung von Primzahlen. Aber jeden Sommer kehrte er zur Martin Company zurück. Wie er später in Harvard sagte: "Die Frage, ob eine praktische Anwendung das hat, was sie dort gelehrt und gelernt hat, war unmöglich, es laut auszusprechen, ganz zu schweigen davon, darüber zu diskutieren ." Bei der Martin Company stellte er jedoch fest, dass die reine Mathematik, die er kannte - sogar Primzahlen - tatsächlich praktische Anwendungen hatte, einschließlich des Schieberegisters.

Im ersten Sommer seiner Arbeit bei der Martin Company wurde Sol einer Management-Theorie-Gruppe zugeordnet. Im zweiten Sommer wurde er in eine Kommunikationsstudiengruppe aufgenommen. Und im Juni 1954 nahm sein Chef an einer Konferenz teil, auf der er von dem seltsamen Verhalten der Verschiebung des linearen Verschiebungsrückkopplungsregisters hörte, und er fragte Saul, ob er diese Forschung durchführen könne. Bald erkannte Sol, dass dieses Thema mit Hilfe von Polynomen über endlichen Feldern untersucht werden konnte. Im nächsten Jahr teilte er seine Zeit zwischen der Harvard Graduate School und der Beratung für die Martin Company auf und schrieb im Juni 1955 seinen Abschlussbericht „ Sequences with Random Properties “, der für die Schieberegistertheorie von grundlegender Bedeutung war.

Sol liebte Mathe-Rätsel, und während er über Rätsel nachdachte , bei denen Domino-Kacheln auf einem Schachbrett angeordnet wurden, erfand er das, was er später " Poliomino " nannte . Er hielt im November 1953 im Harvard Mathematics Club einen Vortrag über sie, veröffentlichte einen Artikel über sie (seine erste Forschungsarbeit) und gewann einen Harvard Mathematics Award für die Zusammenarbeit mit ihnen.



Im Juni 1955 ging Sol für ein Jahr im Rahmen des Fulbright-Stipendienprogramms an die Universität Oslo .- teils um mit einigen prominenten Theoretikern zusammenzuarbeiten, teils um Norwegisch, Schwedisch und Dänisch zu lernen (und einige Runenmanuskripte zu lernen) und um Ihre Sammlung von Sprachkenntnissen aufzufüllen. Während seines Aufenthalts in Oslo verfasste er einen langen Artikel über Primzahlen und schaffte es, durch Skandinavien zu reisen. In Dänemark lernte er eine junge Frau namens Bo (Bodil Rygaard) kennen - sie stammte aus einer großen Familie und wurde in einer Landschaft geboren, die nur für ihre Moore bekannt ist Moos, aber es gelang, an die Universität zu kommen und Philosophie zu studieren. Sol und Bo schienen sich zu verstehen und heirateten einige Monate später.

Als sie im Juli 1956 in die USA zurückkehrten, gab Saul mehrere Interviews und trat dann der JPL bei- Jet Propulsion Laboratory, das vom California Institute of Technology getrennt war und sich mit militärischer Entwicklung befasste. Sol wurde als leitender Forschungsingenieur in das Kommunikationsteam aufgenommen. Zu diesem Zeitpunkt waren die Mitarbeiter des Labors bereit, den Satelliten zu starten. Die Regierung erlaubte es ihnen jedoch nicht, aus Angst, dass es wie eine militärische Aktion aussehen würde. Alles änderte sich im Oktober 1957, als die Sowjetunion ihren Satelliten startete, angeblich im Rahmen des Internationalen Geophysikalischen Jahres . Überraschenderweise brauchten die USA nur drei Monate, um Explorer-1 zu starten. JPL hat viel getan, um den Satelliten zu starten, und die Sol-Gruppe (in der technische Spezialisten an der Implementierung der Registerverschiebung in elektronischer Form arbeiteten) wurde entsandt, um Strahlungsdetektoren zu erstellen. Während dieser Zeit konnte Sol kurz nach Harvard zurückkehren, um die Abschlussprüfung zu bestehen.

Es war eine Zeit der Konzentration um die JPL und das Raumfahrtprogramm. Im Mai 1958 wurde eine neue Informationsverarbeitungsgruppe unter der Leitung von Sol gegründet, und im selben Monat wurde sein erstes Kind geboren - Astrid. Sol setzte seine Untersuchung der Sequenzen fort, die von den Schieberegistern zum Blockieren resistenter Raketen erzeugt wurden. Im Mai 1959 erschien Sols zweite Tochter, die Beatrice hieß (gute Sequenz: A, B ...). Im Herbst 1959 nahm Sol einen akademischen Urlaub am MIT , wo er Claude Shannon und eine Reihe anderer MIT-Leuchten kennenlernte und Theorien über Informationen und algebraische Codes studierte.

Zu dieser Zeit hatte er bereits einige Arbeiten zur Codierungstheorie auf dem Gebiet der Biologie durchgeführt. Trotz der Tatsache, dass Jim Watson und Francis Crick 1953 die digitale Natur der DNA entdeckten , war immer noch nicht klar, wie genau die Sequenzen der vier möglichen Basenpaare 20 Aminosäuren codieren. Im Jahr 1956 Max Delbrück- Watsons ehemaliger Postdoc-Berater bei California Tech - hat sich zu diesem Thema mit dem Jet Propulsion Laboratory beraten. Sol und zwei seiner Kollegen analysierten Francis Cricks Idee und entwickelten „kommafreie Codes“, in denen überlappende Tripel von Basenpaaren Aminosäuren codieren können. Die Analyse ergab, dass auf diese Weise genau 20 Aminosäuren codiert werden können. Dies war eine der erstaunlichsten Erklärungen; Leider funktioniert die Biologie tatsächlich nicht so (die Biologie verwendet eine einfachere Codierung, bei der einige der 64 möglichen Tripel nichts darstellen).

Neben der Biologie studierte Sol auch Physik. Seine von den Schieberegistern erzeugten Sequenzen waren nützlich für die Berechnung der Reichweite unter Verwendung des Radars (verwendet in GPS); auch Sol wurde für die Ermittlung der Entfernung zur Venus verantwortlich gemacht. Und so kam es, dass Sol Anfang 1961, als Sonne, Venus und Erde am erfolgreichsten aufgereiht waren, mit der 85-Fuß- Goldstone -Funkantenne in der Mojave-Wüste ein Radarsignal von der Venus erhielt und die Daten über die Entfernungen zwischen Erde und Venus klärte und Erde-Sonne.

Angesichts des Interesses von Sol an Sprachen, Kodierung und Raum ist es nicht verwunderlich, dass er sich für Außerirdische interessierte. 1961 schrieb er einen Artikel für die Luftwaffe mit dem Titel "Ein kurzer Leitfaden zur außerirdischen Linguistik ", und in den nächsten Jahren schrieb er mehrere Artikel zu diesem Thema für ein breiteres Publikum. Er sagte: " In Bezug auf den Kontakt mit Außerirdischen gibt es zwei Hauptprobleme: Eines davon ist das Problem, einen für beide Seiten akzeptablen Kanal zu finden. Das andere ist mehr philosophisches Problem (semantisch, ethisch und metaphysisch), das darin besteht, das richtige Thema für die Diskussion zu finden. Einfach ausgedrückt, müssen wir zuerst eine gemeinsame Sprache finden und dann überlegen, was wir sagen sollen . "Dann ist es eigenartig er fuhr mit Humor fort: "Natürlich sollten wir ihnen nicht zu viel erzählen, bis wir herausfinden, ob sie genug edle Absichten haben. Die Regierung wird zweifellos eine Space Intelligence Agency (KRU) einrichten, um außerirdische Informationen zu überwachen. Es werden extreme Sicherheitsmaßnahmen ergriffen. Wie Herbert Wells einmal bemerkte [oder war es eine Episode aus der Twilight Zone ?], Dass selbst wenn die Außerirdischen uns aufrichtig sagen, dass ihr einziges Ziel darin besteht, „der Menschheit zu dienen“, wir herausfinden müssen, ob sie uns im Gebackenen oder im Gebackenen dienen wollen gebraten. "

Während seiner Arbeit im JPL-Labor unterrichtete Sol auch an nahe gelegenen Universitäten: dem California Institute of Technology, der University of Southern California und der University of Los Angeles. Im Herbst 1962, nachdem er die Situation im Labor geändert hatte (und vielleicht weil er mehr Zeit mit seinen kleinen Kindern verbringen wollte), beschloss er, Vollzeitprofessor zu werden. Er erhielt Angebote von allen drei Universitäten. Er wollte dorthin gehen, wo er frei arbeiten konnte. Ihm wurde gesagt, dass am California Institute of Technology " niemand außer den Nobelpreisträgern Einfluss hat " und in Los Angeles "es eine solche Bürokratie gibt, dass niemand etwas beeinflussen kann ". Infolgedessen entschied sich Sol trotz seines geringen Ansehens für die University of Southern California. Im Frühjahr 1963 begann er als Professor für Elektrotechnik zu arbeiten und arbeitete dort schließlich 53 Jahre lang.

Schieberegister


Bevor ich die Geschichte von Sauls Leben fortsetze, muss ich erklären, was das lineare Rückkopplungsschieberegister (LFSR) ist. Die Grundidee ist ganz einfach. Stellen Sie sich eine Reihe von Quadraten vor, die jeweils 1 oder 0 enthalten (z. B. schwarz oder weiß). In einem reinen Schieberegister wird alles, was passiert, darauf reduziert, alle Werte einen Schritt nach links zu verschieben, während der Wert ganz links verloren geht und der neue Wert nach rechts verschoben wird. Die Idee eines Rückkopplungsschieberegisters besteht darin, dass der Wert, der verschoben wird, in Abhängigkeit von den Werten anderer Positionen im Schieberegister bestimmt (oder "zurückgemeldet") wird. In einem linearen Schieberegister mit Rückkopplung werden die Werte aus den "Zweigen" an bestimmten Positionen im Register mit Modulo 2 kombiniert (so dass 1⊕1 = 0 statt 2 ist) oder XOR (" exklusiv oder ") angewendet .



Nach einer Weile passiert Folgendes:



Wie Sie sehen können, verschiebt das Schieberegister die Bits immer nach links, und andere Bits werden nach einer einfachen Regel nach rechts hinzugefügt. Die Folge von Bits scheint zufällig zu sein, obwohl sie sich, wie in der Abbildung gezeigt, schließlich wiederholt. Sol Golomb fand einen eleganten mathematischen Weg, um solche Sequenzen zu analysieren und wie sie wiederholt werden.

Wenn das Schieberegister die Größe n hat, hat es 2 n mögliche Zustände (entsprechend allen möglichen Sequenzen 0 und 1 mit der Länge n) Da die Regeln für das Schieberegister deterministisch sind, sollte jede gegebene Position immer an eine andere gleiche Position kommen. Dies bedeutet, dass die maximal mögliche Anzahl von Schritten, die das Schieberegister durchlaufen kann, bevor sich die Schritte zu wiederholen beginnen, 2 n beträgt (tatsächlich 2 n - 1, da sich die Position mit allen 0 nicht zu etwas anderem entwickeln kann).

Im obigen Beispiel hat das Schieberegister die Größe 7 und wiederholt sich genau nach 2 7 - 1 = 127 Schritten. Aber welche Schieberegister - mit welchen Verzweigungsorten - erzeugen Sequenzen maximaler Länge? Diese Frage begann Solomon Golomb im Sommer 1954 zu untersuchen. Und seine Antwort war einfach und elegant.

Das obige Schieberegister hat Verzweigungen an den Positionen 7, 6 und 1. Sol präsentierte dies algebraisch unter Verwendung des Polynoms x 7 + x 6 + 1. Er zeigte dann, dass die erzeugte Sequenz von maximaler Länge sein wird, wenn dieses Polynom „ irreduzibles Modulo 2 “ ist; daher kann es nicht faktorisiert werden, was es zu einem Analogon einer Primzahl unter Polynomen macht; und das Vorhandensein einiger anderer Eigenschaften macht es zu einem " primitiven Polynom ". Heute ist dies mit dem Mathematica- System und der Wolfram-Sprache leicht zu überprüfen :



Dann, 1954, musste Sol dies alles manuell tun; er stellte eine ziemlich lange Tabelle primitiver Polynome zusammen, die Schieberegistern entsprachen, die Sequenzen maximaler Länge erzeugten:



Hintergrund des Schieberegisters


Die Idee, RAM über die " Verzögerungsleitungen " aufrechtzuerhalten , die digitale Impulse übertragen, geht auf den Beginn der Ära der Computer zurück. Ende der 1940er Jahre wurden solche Verzögerungsleitungen mit einer Reihe von Vakuumröhren digital angelegt und als „ Schieberegister “ bezeichnet. Es ist nicht klar, wann die ersten Rückkopplungsschieberegister erstellt wurden. Vielleicht war das Ende der 1940er Jahre. Dieses Ereignis ist jedoch immer noch rätselhaft, da sie zum ersten Mal in der militärischen Kryptographie verwendet wurden.

Die Hauptidee der Kryptographie besteht darin, sinnvolle Nachrichten so zu ändern, dass sie nicht erkannt werden können. Wenn Sie den Schlüssel kennen, können Sie die verschlüsselte Nachricht neu erstellen. Die sogenannten Stream-Chiffren arbeiten nach dem Prinzip, sozusagen lange Folgen zufälliger Elemente zu erzeugen, und werden mit einem Empfänger dekodiert, der unabhängig voneinander die gleiche Folge von Elementen erzeugt.

Lineare Rückkopplungsschieberegister wurden in der Kryptographie aufgrund langer Wiederholungsperioden bewertet. Die mathematische Analyse, die Sol verwendet hat, um diese Perioden zu finden, macht jedoch deutlich, dass solche Schieberegister nicht für eine sichere Kryptographie geeignet sind. Am Anfang schienen sie jedoch recht gut zu sein (insbesondere im Vergleich zu den aufeinanderfolgenden Rotorpositionen in Enigma); Es kursierten anhaltende Gerüchte, dass sowjetische militärische Kryptosysteme auf dieser Grundlage gebaut wurden.

Als ich 2001 an historischen Notizen für mein Buch A New Kind of Science arbeitete , sprachen Sol und ich lange telefonisch über Registerverschiebungen. Saul erzählte mir, dass er zu Beginn nichts über kryptografische Arbeiten an Schieberegistern wusste. Er sagte, dass die Mitarbeiter von Bell's Labor, Lincoln's Labor und Jet Propulsion Laboratory ungefähr zur gleichen Zeit wie er mit der Arbeit an den Schieberegistern begannen. es gelang ihm jedoch, ein wenig weiter voranzukommen, was er in seinem Bericht von 1955 feststellte.

In den folgenden Jahren lernte Sol nach und nach die verschiedenen Vorgänger seiner Arbeit aus der Literatur zur reinen Mathematik kennen. Bereits 1202Fibonacci sprach über das, was jetzt Fibonacci-Zahlen genannt wird und die durch eine Wiederholungsrelation erzeugt werden (die als Analogon des linearen Rückkopplungsschieberegisters betrachtet werden kann, das mit beliebigen ganzen Zahlen anstelle von Nullen und Einsen arbeitet). Es gibt auch kleine Werke des frühen 20. Jahrhunderts in den Zyklen 0 und 1, aber die erste groß angelegte Studie war das Werk von Oysten Ore von der Universität Oslo. Ore hatte einen Studenten namens Marshall Hall , der einen Vorgänger der National Security Agency berietin den späten 1940er Jahren - wahrscheinlich zum Thema Schieberegister. Alles, was er tat, wurde jedoch klassifiziert, und deshalb vereinbarte er mit Sol, die Geschichte der Schieberegister mit linearer Rückkopplung zu veröffentlichen. Saul widmete sein Buch Marshall Hall.

Warum brauchen wir Sequenzen, die von Schieberegistern erzeugt werden?


Ich habe oft bemerkt, dass Systeme, die durch einfache Regeln definiert sind, viele Anwendungsvarianten aufweisen. Schieberegister folgen ebenfalls diesem Muster. Sowohl moderne Geräte als auch Software sind mit Schieberegistern vollgestopft: Es gibt wahrscheinlich ein Dutzend oder zwei davon in einem herkömmlichen Mobiltelefon, die normalerweise auf Hardwareebene und manchmal in Software implementiert sind (wenn ich hier „Schieberegister“ schreibe, ich Ich meine das lineare Rückkopplungsschieberegister (LFSR).

In den meisten Fällen werden Schieberegister verwendet, die Sequenzen maximaler Länge ergeben (auch als " M-Sequenzen" bekannt)."). Die Gründe, warum sie verwendet werden, hängen normalerweise mit einigen ihrer Eigenschaften zusammen, die Sol entdeckt hat. Sie enthalten immer die gleiche Menge von 0 und 1 (obwohl es tatsächlich immer genau eine zusätzliche 1 gibt). Anschließend zeigte Sol, dass sie Die gleiche Anzahl von Sequenzen 00, 01, 10 und 11 ist ebenfalls charakteristisch - und auch für große Blöcke ist diese Eigenschaft von " balance " an sich schon sehr nützlich, wenn Sie beispielsweise alle möglichen Kombinationen von Bits als Eingabe testen.

Sol fand jedoch eine andere, noch wichtigere Eigenschaft. Ersetzen Sie jede 0 in der Sequenz durch 1 und multiplizieren Sie dann jedes Element in der verschobenen Version der Sequenz mit dem entsprechenden Element im Original. Sol hat gezeigt, dass diese Elemente beim Hinzufügen immer Null sind (außer wenn es überhaupt keine Verschiebung gibt). Das heißt, die Sequenz hat keine Korrelation mit verschobenen Versionen von sich.

Diese Eigenschaften gelten für jede ausreichend lange zufällige Folge von 0 und 1. Es ist überraschend, dass diese Eigenschaften für Folgen maximaler Länge immer zutreffen. Sequenzen haben einige Merkmale der Zufälligkeit, aber in Wirklichkeit sind sie überhaupt nicht chaotisch: Sie haben eine klar definierte, organisierte Struktur .

Es ist diese Struktur, die für lineare Rückkopplungsschieberegister charakteristisch ist, die sie für eine ernsthafte Kryptographie ungeeignet macht. Sie eignen sich jedoch hervorragend für die grundlegende "Neuanordnung von Elementen" und die billige Kryptographie und werden für diese Zwecke aktiv verwendet. Oft besteht die Aufgabe einfach darin, das Signal „aufzuhellen“ (wie bei „weißem Rauschen“). Manchmal müssen Sie Daten mit langen Folgen von 0 übertragen. In diesem Fall kann die Elektronik jedoch verwirrt werden, wenn die "Stille" zu lang ist. Sie können dieses Problem vermeiden, indem Sie die Quelldaten verschlüsseln, indem Sie sie mit der vom Schieberegister generierten Sequenz kombinieren. Genau das wurde mit Wi-Fi , Bluetooth , USB , digitalem Fernsehen , Internet usw. gemacht.

Ein Nebeneffekt des Verwürfelns von Schieberegistern ist eine komplexere Decodierung, die manchmal zur Erhöhung der Sicherheit verwendet wird (die DVD- Technologie verwendet eine Kombination von Schieberegistern mit einer Länge von 16 und 24 Bit zum Codieren von Daten; viele GSM- Telefone verwenden eine Kombination von drei Schieberegistern zum Codieren aller Signale).

In GPSSchieberegistersequenzen werden ebenfalls verwendet. Jeder GPS-Satellit sendet kontinuierlich eine Sequenz, die durch ein Schieberegister mit einer Länge von 10 Bit erzeugt wird. Basierend auf dem empfangenen Teil der Sequenz kann der Empfänger genau bestimmen, zu welchem ​​Zeitpunkt das empfangene Signal von einem bestimmten Satelliten gesendet wurde. Durch Vergleichen der Zeitverzögerung von verschiedenen Satelliten kann der Empfänger seine Position triangulieren (es gibt auch einen GPS-Modus, der ein Schieberegister mit einer Länge von 1024 Bit verwendet).



Ganz anders werden Schieberegister verwendet, um Fehler zu erkennen. Angenommen, jemand sendet Bitblöcke, und für jeden von ihnen besteht eine geringe Fehlerwahrscheinlichkeit. Eine einfache Möglichkeit, nach einem einzelnen Fehler zu suchen, besteht darin, das " Paritätsbit " zu aktivieren .", die angibt, wie viele 1 (ungerade oder gerade Zahl) im Bitblock enthalten sein sollen. Sie können auch CRC (Cyclic Redundancy Checks) verwenden, die nach mehr Fehlern suchen können. Diese werden berechnet, indem Daten mit linearer Rückkopplung an das Schieberegister gesendet werden Es gibt auch Fehlerkorrekturcodes, mit denen eine bestimmte Anzahl von Fehlern nicht nur erkannt, sondern auch korrigiert werden kann. Einige von ihnen können auch anhand der von den Schieberegistern generierten Sequenzen berechnet werden - und mit Sol Golomb Er nannte Versionen dieser Codes, Reed-Solomon-Codes genannt , um Videos für ein Raumschiff zum Mars zu kodieren.

Der Umfang der von Schieberegistern erzeugten Sequenzen wird immer größer. Es gibt ein ziemlich exotisches Beispiel für die Verwendung von Sequenzen, die von Schieberegistern generiert wurden, um Jitter in einem Computer zu takten - die Zerlegung der Frequenz, bei der der Prozessor möglicherweise Hochfrequenzstörungen erzeugen kann (wählen Sie im BIOS „Spread Spectrum aktivieren“).

Eine der bekanntesten Anwendungen von Schieberegistersequenzen ist CDMATelefone (Code Division Multiple Access). Mobiltelefone haben ihren Namen erhalten, weil sie in „Zellen“ arbeiten und alle Telefone einer bestimmten Zelle mit einem bestimmten Turm verbunden sind. Aber wie stören sich verschiedene Handys in der „Zelle“ nicht? In den ersten Systemen „stimmte“ jedes Telefon einfach mit dem Turm überein, eine etwas andere Frequenz zu verwenden. Später wurden verschiedene Zeitscheiben verwendet ( TDMA - Time Division Multiple Access). Und CDMA verwendet als vernünftige Alternative Schieberegistersequenzen mit maximaler Länge.

Die Idee ist, dass alle Telefone auf derselben Frequenz arbeiten, aber jedes Telefon sein eigenes Signal unter Verwendung (im einfachsten Fall) verschiedener Versionen der von den Schieberegistern erzeugten Sequenzen codiert. Nach Sols Ergebnissen korrelieren verschiedene Schaltoptionen nicht miteinander, und daher stören Handysignale nicht. So funktionieren die meisten 3G- Netze .

Sol schuf die mathematische Grundlage für all dies und führte sich auch wieder in eine Reihe von Schlüsselfiguren ein. Bereits 1959 traf er Irwin Jacobs , der kürzlich am Massachusetts Institute of Technology promovierte. Er kannte auch Andy Viterbi.der im Jet Propulsion Laboratory arbeitete. Sol stellte sie vor und 1968 gründeten sie eine Firma namens Linkabit , die an Codierungssystemen arbeitete (hauptsächlich für militärische Zwecke).

1985 gründeten Jacobs und Viterbi eine weitere Firma namens Qualcomm . Anfangs lief es nicht gut mit ihnen, aber Anfang der neunziger Jahre, als sie anfingen, Komponenten für den Einsatz von CDMA in Mobiltelefonen herzustellen, begann das Unternehmen schnell zu wachsen.

Wo sind diese Register?


Überraschenderweise haben die meisten Menschen noch nie von Schieberegistern gehört und interagieren gleichzeitig mit ihnen, wenn sie moderne Kommunikationssysteme, Computertechnologie usw. verwenden. Es ist leicht zu verwechseln, da dieselbe Registerfolge hinter verschiedenen Namen und Abkürzungen steht lineare Rückkopplungsverschiebung (PN, Pseudorauschen, M-, FSR-, LFSR-Sequenzen, MLS, SRS, PRBS usw.).

Wenn wir Mobiltelefone betrachten, hat sich die Verwendung von Sequenzen, die durch Schieberegister in ihnen erzeugt werden, im Laufe der Jahre geändert und nimmt zu und ab. 2GNetzwerke basieren auf TDMA, verwenden also nicht die von den Schieberegistern erzeugten Sequenzen, um ihre Daten zu codieren, verwenden jedoch häufig CRC (Cyclic Redundancy Code), um Datenblöcke zu überprüfen. 3G- Netze sind die größten Benutzer von CDMA, daher sind die von den Schieberegistern erzeugten Sequenzen an der Übertragung jedes Bits beteiligt. 4G- Netzwerke verwenden normalerweise eine Kombination aus Zeit und Frequenz von Slots, die keine Schieberegistersequenzen enthalten, obwohl CRCs immer noch verwendet werden: zum Beispiel, um mit integralen Daten zu interagieren, wenn sich die Frequenzfenster überlappen. 5gEs hat eine komplexere Struktur - mit vielen Antennen, die sich dynamisch anpassen, um die optimale Zeit und Schlitzfrequenz zu nutzen. Die Hälfte ihrer Kanäle wird jedoch normalerweise für „Pilotsignale“ zugewiesen, die zur Ableitung der lokalen Funkumgebung verwendet werden. Sie basieren auch auf den Sequenzen, die von den Schieberegistern erzeugt werden.

Bei der Herstellung von Elektronik versuchen sie normalerweise, die höchste Datenübertragungsrate bei minimalem Energieverbrauch zu erreichen, wodurch die Bits die Rauschschwelle überwinden können. Und dieser Weg führt in der Regel zur Automatisierung der Fehlererkennung und damit zur Verwendung von CRC (Cyclic Redundancy Code) und damit der vom Schieberegister erzeugten Sequenzen. Dies gilt für fast alle Arten von Bussen im Computer ( PCIe ,SATA usw.): Bereitstellung der Interaktion von Teilen des Zentralprozessors oder Empfang von Daten von Geräten oder Verbindung mit einem Display mit HDMI . Im Fall von Platten oder Speicher werden CRC und andere Codes, die auf den von den Schieberegistern erzeugten Sequenzen basieren, auch fast universell verwendet, um mit maximaler Geschwindigkeit zu arbeiten.

Schieberegister sind so allgegenwärtig, dass es fast unmöglich ist, abzuschätzen, wie viele Bits sie erzeugen. Das integrierte IoT ("Internet der Dinge") enthält ungefähr 10 Milliarden Computer, etwas weniger Telefone und eine große Anzahl von Geräten . Fast jedes Auto auf der Welt (und es gibt mehr als eine Milliarde davon!) Hat ungefähr 10 eingebaute Mikroprozessoren.

Mit welcher Frequenz arbeiten Schieberegister? In Kommunikationssystemen gibt es eine Basisträgerfrequenz im Hertz-Bereich sowie eine "Signalelement-Übertragungsrate", die angibt, wie schnell ein Mehrfachzugriff (wir sprechen von CDMA) im MHz-Bereich durchgeführt wird. Andererseits werden in Bussen in Computern alle Daten über Schieberegister übertragen - mit der besten Übertragungsgeschwindigkeit im Hertz-Bereich.

Es gibt mindestens 10 Milliarden Kommunikationsleitungen, die mindestens 1/10 Milliarden Sekunden (ungefähr 3 Jahre) arbeiten und jede Sekunde mindestens 1 Milliarde Bits aus den Schieberegistern verwenden, was bedeutet, dass dies der Sol-Algorithmus war mindestens eine Oktillion Mal verwendet.

Wird dieser Algorithmus wirklich am häufigsten verwendet? Ich denke ja. Ich vermute, dass nur arithmetische Operationen konkurrieren können. Heutzutage können Prozessoren Billionen arithmetische Operationen pro Sekunde ausführen, und solche Operationen sind für fast jedes von einem Computer erzeugte Bit erforderlich. Aber wie wird gerechnet? In gewisser Hinsicht ist es nur eine Implementierung der digitalen Elektronik.

Es gibt jedoch „algorithmische Ideen“, die für alle außer für Mikroprozessor-Designer unverständlich bleiben. Als Babbage seine Differenzmaschine machte (siehe den Artikel über Habra " Entwirren der Geschichte von Ada Lovelace (dem ersten Programmierer in der Geschichte)"") wurden Übertragungen zu einem großen Hindernis für arithmetische Operationen (tatsächlich kann ein Schieberegister mit linearer Rückkopplung als ein System angesehen werden, das so etwas wie arithmetische Berechnungen ausführt, aber keine Übertragung ausführt). Es gibt" Übertragungssignal-Ausbreitungsbäume " "Optimierung der Silbentrennung. Es gibt auch kleine Tricks (wie den" Booth-Algorithmus "," Wallace-Bäume)"usw.), die die Anzahl der Bitoperationen reduzieren, die zum Erstellen der" Interna "der Arithmetik erforderlich sind. Im Gegensatz zu Schieberegistern mit linearer Rückkopplung gibt es jedoch keine einzige algorithmische Idee, die fast überall verwendet werden würde Ich denke, dass die längsten möglichen Sequenzen, die durch lineare Rückkopplungsschieberegister erzeugt werden, immer noch unter den am häufigsten verwendeten Sequenzen gewinnen.

Zelluläre Automaten und Schieberegister mit nichtlinearer Rückkopplung


Obwohl dies auf den ersten Blick nicht offensichtlich erscheint, stellt sich heraus, dass es eine enge Beziehung zwischen Schieberegistern mit Rückkopplung und zellularen Automaten gibt, die ich seit vielen Jahren untersucht habe. Die grundlegende Organisation für ein Rückkopplungsschieberegister besteht darin, jeweils ein Bit zu berechnen. In einem zellularen Automaten gibt es eine Reihe von Zellen, und bei jedem Schritt werden alle Zellen parallel aktualisiert, basierend auf einer Regel, die beispielsweise von den Werten ihrer nächsten Nachbarn abhängt.

Um zu sehen, wie sie zusammenhängen, müssen Sie das Schieberegister mit einer Rückmeldung der Größe n starten und gleichzeitig nur alle n seinen Status anzeigenSchritte; Mit anderen Worten, lassen Sie zu, dass alle Bits überschrieben werden, bevor sie wieder angezeigt werden. Wenn jeder Schritt des Schieberegisters mit linearer Rückkopplung angezeigt wird (hier mit zwei Zweigen), verschiebt sich bei jedem Schritt alles nach links - und das war's. Wenn Sie jedoch ein komprimiertes Bild erstellen, das nur alle n Schritte zeigt, wird ein Muster angezeigt.



Dies ist ein verschachteltes Muster. und dieses Bild ist dem sehr ähnlich, das erhalten werden kann, wenn der zellulare Automat die Zelle und die benachbarte nimmt und sie Modulo 2 (XOR) hinzufügt. Dies passiert mit einem zellularen Automaten, wenn er seine Zellen so anordnet, dass sie sich in einem Kreis mit der gleichen Größe wie das Schieberegister oben befinden:



Zunächst stellen sich heraus, dass zellulare Automaten und Schieberegistermuster genau gleich sind. Wenn Sie sich diese Bilder ansehen, wird es weniger überraschend, dass die Mathematik von Schieberegistern mit zellularen Automaten in Beziehung gesetzt werden sollte. Und angesichts der Wiederholbarkeit verschachtelter Muster wird klar, warum eine elegante mathematische Theorie der Schieberegister existieren muss.

Für typische Schieberegister, die in der Praxis verwendet werden, sind solche sich explizit wiederholenden Muster nicht charakteristisch. Hier sind einige Beispiele für Schieberegister, die Sequenzen maximaler Länge erzeugen. Tatsache ist, dass die Zweige weit voneinander entfernt sind, was es schwierig macht, visuelle Spuren von Verschachtelungen zu finden.



Wie groß ist die Korrespondenz zwischen Schieberegistern und zellularen Automaten? Für zellulare Automaten können die Regeln zum Generieren neuer Zellenwerte beliebig sein. In linearen Rückkopplungsschieberegistern sollten sie immer auf der Addition von Modulo 2 (oder XOR) basieren. Dies ist, was der "lineare" Teil des "linearen Rückkopplungsschieberegisters" bedeutet. Es ist auch möglich, eine beliebige Regel zu verwenden, um Werte für Schieberegister mit nichtlinearer Rückkopplung (NFSR) zu kombinieren.

In der Tat: Als Sol seine Theorie für lineare Rückkopplungsschieberegister entwickelte, begann er mit einem nichtlinearen Fall. Als er 1956 bei JPL ankam, erhielt er ein Labor, das mit Gestellen für kleine elektronische Module ausgestattet war. Saul sagte, dass die Module (jedes von der Größe einer Zigarettenschachtel) für das Bell Labs-Projekt gebaut wurden, um eine bestimmte logische Operation durchzuführen (UND, ODER, NICHT, ...). Die Module können zusammen verwendet werden, um beliebige nichtlineare Rückkopplungsschieberegister zu implementieren, die ungefähr eine Million Bits pro Sekunde liefern (Sol sagte mir, dass jemand versucht hat, dasselbe mit einem Universalcomputer zu tun, und dies dauerte 1 Sekunde, wenn er verwendet wurde Bei Hardwaremodulen dauerte die Arbeit an einem Universalcomputer 6 Wochen.

Als Sol begann, Schieberegister mit linearer Rückkopplung zu studieren, war seine erste ernsthafte Entdeckung die Zeiträume ihrer Wiederholung. Und im Fall von nichtlinear richtete er die meisten seiner Bemühungen darauf, dasselbe zu verstehen. Er sammelte alle Arten von experimentellen Daten. Er erzählte mir, dass er sogar Sequenzen von 2.445 überprüfte , was ein Jahr dauerte. Er machte eine Zusammenfassung, wie im Bild unten (achten Sie auf die Visualisierung der auf der Wellenformlinie gezeigten Sequenzen). Es gelang ihm jedoch nie, eine allgemeine Theorie zu entwickeln, die er für lineare Rückkopplungsschieberegister hatte.


 
Kein Wunder, dass er es nicht konnte. Bereits in den 1950er Jahren erschienen theoretische Ergebnisse (in den meisten Fällen basierend auf den Ideen universeller Turing- Berechnungen)), von denen Programme dies grundsätzlich tun könnten. Ich glaube nicht, dass Sol oder sonst jemand jemals gedacht hat, dass sehr einfache (nichtlineare) Funktionen in Schieberegistern mit nichtlinearer Rückkopplung verwendet werden.

Und erst später wurde klar, wie komplex das Verhalten selbst sehr einfacher Programme sein kann. Mein Lieblingsbeispiel ist Regel 30 für einen zellularen Automaten, bei dem die Werte benachbarter Zellen mit einer Funktion kombiniert werden, die als p + q + r + q * r mod 2 (oder p XOR ( q OR r ) dargestellt werden kann.) Unglaublicherweise betrachtete Sol Schieberegister mit nichtlinearer Rückkopplung basierend auf ähnlichen Funktionen: p + r + s + q * r + q * s + r * s mod 2 . Im Folgenden finden Sie Abbildungen, wie die Sol-Funktion (die als „ Regel 29070 “ angesehen werden kann), Regel 30 und einige andere ähnliche Regeln im Schieberegister aussehen:



Hier sind sie jedoch nicht auf ein Register mit fester Größe beschränkt, sondern sehen aus wie zellulare Automaten:



Natürlich hat Sol nie solche Bilder gemacht (und das war in den 1950er Jahren fast unmöglich). Stattdessen konzentrierte er sich auf die Wiederholungsperiode als eine Art aggregiertes Merkmal.

Saul fragte sich, ob Schieberegister mit nichtlinearer Rückkopplung Zufallsquellen sein könnten. Aus dem, was heute über zellulare Automaten bekannt ist, ist klar, dass dies möglich ist. Um beispielsweise Zufälligkeit für das Mathematica-System zu erzeugen, haben wir 25 Jahre lang die Regel von 30 zellularen Automaten verwendet (obwohl wir sie kürzlich zugunsten einer effizienteren Regel aufgegeben haben, die wir durch die Untersuchung von Billionen von Möglichkeiten gefunden haben).

Sol sprach ein wenig über Verschlüsselung; obwohl ich denke, dass er nicht lange für die Regierung gearbeitet hat. Er erzählte mir, dass er, obwohl er 1959 " mehrdimensionale Korrelationsangriffe auf nichtlineare Sequenzen " entdeckte, " Vorwürfe, das Programm sei für die Kryptoanalyse bestimmt ", sorgfältig vermieden habe"Tatsache ist, dass Regel 30 für zellulare Automaten (und möglicherweise auch Schieberegister mit nichtlinearer Rückkopplung) gute Kryptosysteme sein kann - obwohl sie aufgrund der Tatsache, dass sie Schieberegistern mit linearer Rückkopplung zu entsprechen scheinen (und dies auch) nicht), sie wurden nie so oft wie möglich verwendet.

Als Enthusiast habe ich in den letzten Jahrzehnten versucht, alle Vorgänger meiner Arbeit an eindimensionalen zellulären Automaten zu studieren. Zweidimensionale zelluläre Automaten wurden ein wenig untersucht, aber im Fall von od Nur eine rein theoretische Arbeit wurde durch Zahlen gefunden. Ich denke, dass nach allem, was ich sah, die Schieberegister mit nichtlinearer Rückkopplung von Solomon Golomb dem am nächsten kamen, was ich schließlich ein Vierteljahrhundert später tat.

Poliomino


Wenn viele den Namen " Golomb " hören, werden sie sich an die Schieberegister erinnern. Die meisten werden sich jedoch an Poliomino erinnern . Sol hat Poliomino nicht erfunden, obwohl er den Namen geprägt hat. Er machte systematisch, was früher nur in einzelnen Rätseln vorkam.

Die Hauptfrage, die Sol interessierte, war, wie Poliomino-Sets für einen bestimmten Bereich organisiert werden könnten. Manchmal ist es ziemlich offensichtlich und manchmal ist es ziemlich kompliziert. Sol veröffentlichte 1954 seinen ersten Artikel über Poliomino, aber Martin Gardner machte Poliomino 1957 sehr beliebt (er schrieb eine Kolumne über mathematische Spiele in Scientific American) Wie Sol im Vorwort zu seinem Buch von 1964 erklärte, erhielt er als Ergebnis "einen ständigen Strom von Korrespondenten aus der ganzen Welt und aus allen Lebensbereichen: Vorsitzende des Verwaltungsrates führender Universitäten, Bewohner unbekannter Klöster, die in berühmten Gefängnissen inhaftiert sind ... ".

Spielefirmen wandten sich auch neuen Rätseln zu, und im Laufe mehrerer Monate erschienen Schlagzeilen wie „ neue sensationelle Rätsel “, gefolgt von Jahrzehnten anderer Rätsel und Spiele, die auf Poliomino basierten (nein, der finstere Glatzkopf sieht nicht aus wie Sol): Sol gedruckte Artikel über Poliomino für weitere 50 Jahre nach der ersten Veröffentlichung. 1961 führte er Optionen für die Aufteilung von Rep-Kacheln in kleine Teile ein









", mit dem Sie fraktale Muster (" Infin-Tile ") erstellen können. Aber fast alles, was Sol mit Poliomino gemacht hat, beinhaltete das Lösen spezifischer Probleme.

Ich interessiere mich nicht sehr für die Besonderheiten von Poliomino; ich interessiere mich für verwandte Phänomene allgemeinerer Natur . Es scheint leicht zu entscheiden, ob es möglich ist, das gesamte Flugzeug mit ein paar einfachen Formen zu „überbrücken“, aber im Fall von Poliomino (sowie bei allen darauf basierenden Spielen und Rätseln) wird klar, dass nicht alles so einfach ist. in der Tat - in den 1960er Jahren wurde bewiesen, dass diese Aufgabe theoretisch war nische unlösbare .

Wenn wir nur an einem begrenzten Bereich interessiert sind, können Sie im Prinzip einfach alle denkbaren Anordnungen von Figuren auflisten und dann prüfen, ob sie richtig angeordnet sind. Wenn wir jedoch an Unendlichkeit interessiert sind, kann dies nicht getan werden. Vielleicht findet jemand die Möglichkeit, eine Million Stücke erfolgreich zu platzieren, aber es gibt keine Garantie dafür, dass dieses Ergebnis weiter verbreitet werden kann.

Es stellt sich heraus, dass es wie eine funktionierende Turing-Maschine aussehen könnte- oder ein zellularer Automat. Sie beginnen mit einer Reihe von Kacheln. Dann ist die Frage, ob eine unendliche Kachelung möglich ist, gleichbedeutend mit der Frage, ob eine Installation für eine Turing-Maschine möglich ist, die es ihr ermöglicht, nicht anzuhalten. Tatsache ist, dass, wenn die Turing-Maschine universell ist (das heißt, sie kann so programmiert werden, dass sie mögliche Berechnungen durchführt), das Stoppproblem für sie unlösbar sein kann, was bedeutet, dass das Kachelproblem auch unlösbar ist.

Dies hängt natürlich von den ursprünglichen Formularen ab. Die Frage ist, wie kompliziert die Formulare sein müssen, um universelle Berechnungen zu codieren und zu dem unlösbaren Problem der Kacheln zu führen. Solomon Golomb wusste über die Literatur zu diesem Thema Bescheid, war aber nicht besonders daran interessiert.

Es ist bekannt, dass hoch entwickelte und sorgfältig entworfene Polimino-Sets tatsächlich Universal Computing unterstützen. Aber was ist mit einem einfachen Set? Ist er wirklich einfach genug, um versehentlich über ihn zu stolpern? Wenn Sie sich alle Systeme ansehen, die ich untersucht habe, stellt sich heraus, dass der einfachste Satz wirklich einfach ist. Es ist jedoch schwer zu finden.

Eine viel einfachere Aufgabe besteht darin, Poliominos zu finden, die Flugzeuge erfolgreich füllen, wenn auch nur nicht periodisch. Roger Penrose fand 1994 ein geeignetes Beispiel. In meinem Buch A New Kind of Science habe ich ein etwas einfacheres Beispiel mit 3 Poliominoes gegeben:



Rest der Geschichte


Saul war etwas mehr als dreißig Jahre alt, als er bemerkenswerte Erfolge im Bereich Schieberegister und Poliomino erzielte ... Er war ein sehr aktiver Mensch. Er schrieb mehrere hundert Artikel , von denen einige seine früheren Arbeiten erweiterten, einige waren Antworten auf Fragen, die ihm gestellt wurden, und einige wurden anscheinend nur zum Spaß geschrieben - um interessante Dinge über Zahlen, Sequenzen, Kryptosysteme usw. herauszufinden. . q

Schieberegister und poliomino - Volume Fäden (sie auch in den einzelnen Kategorien in der angezeigten AMS - Klassifizierung) In den letzten Jahrzehnten erhielten beide eine neue Entwicklungsrunde, als sie begannen, auf ihrer Basis Computerexperimente durchzuführen. Sol nahm auch aktiv an ihnen teil. Viele Fragen bleiben jedoch unbeantwortet. Und wenn große Hadamard-Matrizen für Schieberegister mit linearer Rückkopplung gefunden werden können , ist selbst jetzt noch wenig über Schieberegister mit nichtlinearer Rückkopplung bekannt, ganz zu schweigen von allen nichtperiodischen und anderen exotischen Poliominos.

Sol war schon immer an Rätseln interessiert, sowohl an Mathematik als auch an Wörtern. Einige Zeit leitete er eine Reihe von Rätseln für die Los Angeles Times und 32 Jahre lang schrieb er " Golomb Gambits " in der Alumni-Zeitschrift John Hopkins. Er nahm am Testen von MegaIQ teilund gewann eine Reise ins Weiße Haus, als er und sein Chef die Top 5 des Landes betraten.

Er hat viel Mühe in seine Arbeit an der Universität gesteckt: Er unterrichtete nicht nur Studenten und betreute Doktoranden und stieg die Verwaltungsleiter hinauf (Präsident des Universitätsrates, Vizerektor für Forschung usw.), sondern äußerte auch seine Meinung zur Leitung der Universität als Ganzes (zum Beispiel) schrieb einen Artikel mit dem Titel "Beratung an der Fakultät: entfernen oder verlassen?" ; Antwort: Nein, das ist gut für die Universität!). An der University of Southern California beschäftigte er sich mit Headhunting und half der Universität während seiner Arbeit, vom Unbekannten an die Spitze der Bewertung von Bildungsprogrammen aufzusteigen.

Und dann gab es Beratung. Sol war akribisch und gab nicht bekannt, was er für Regierungsorganisationen tat. Ende der 60er Jahre gründete Sol das Unternehmen, das er Recreational Technology, Inc. nannte, enttäuscht darüber, dass alle außer ihm mit dem Verkauf von Spielen auf Poliomino-Basis beschäftigt waren. Die Dinge liefen nicht gut, aber Sol lernte Alvin Burlekamp kennen , einen Professor in Berkeley, der sich für das Codieren von Theorien und Rätseln interessierte. Anschließend gründeten sie Cyclotomics (zu Ehren von zyklotomischen Polynomen der Form x n - 1), die schließlich für eine runde Summe an Kodak verkauft wurden (Berlekamp schuf auch ein algorithmisches Handelssystem, das er dann an Jim Simons verkaufteund der zum Ausgangspunkt für Renaissance Technologies wurde - einer der bislang größten Hedgefonds).

Mehr als 10.000 Patente hängen irgendwie mit der Arbeit von Saul zusammen, aber Sol selbst erhielt nur ein Patent für Kryptosysteme, die auf Quasigruppen basieren - und ich denke, dass er wenig getan hat, um seine Arbeit zu kommerzialisieren.

Im Laufe der Jahre hat Sol mit dem Technion , einem israelischen Technologieinstitut, zusammengearbeitet. Er sprach von sich selbst als „ nicht-religiös-orthodoxer Jude “, unterrichtete aber manchmal auch Seminare zum Buch Genesis für Anfänger und arbeitete auch an der Entschlüsselung von Teilen der Schriftrollen vom Toten Meer (Qumran-Manuskripte).

Saul und seine Frau reisten viel, aber Sauls "Zentrum der Welt" war definitiv sein Büro in Los Angeles an der University of Southern California und das Haus, in dem er und seine Frau fast 60 Jahre lang gelebt hatten. Er war immer von Freunden und Studenten umgeben. Und er hatte eine Familie. Seine Tochter Astrid spielte die Rolle einer Studentin in einem Stück über Richard Feynman (sie posierte für ihn) und im Roman meines Freundes als eine der Figuren. Beatrice widmete ihre Karriere der Anwendung des mathematischen Genauigkeitsniveaus auf verschiedene Arten von medizinischen Indikationen und Diagnosen (Krankheiten im Zusammenhang mit dem Golfkrieg, Statineffekte, Schluckaufattacken usw.). Ich habe sogar einen kleinen Beitrag zu Beatrices Leben geleistet, indem ich sie dem Mann vorgestellt habe, der später ihr Ehemann wurde - Terry Seinowski, einer der Begründer der modernen Computational Neuroscience.

Es schien, dass Saul an vielen Ereignissen beteiligt war, auch wenn er nicht zu viel über die Details verbreitete. Von Zeit zu Zeit wollte ich mit ihm über Naturwissenschaften und Mathematik sprechen, aber er war mehr daran interessiert, Geschichten (oft sehr faszinierend) sowohl über Einzelpersonen als auch über Organisationen zu erzählen (" Kannst du das [1985] nach vielen Jahren der Abwesenheit glauben?") Auf Konferenzen erschien Claude Shannon nur ohne Vorwarnung an der Bar der jährlichen Konferenz über Informationstheorie? ";" Wissen Sie, wie viel sie dem Leiter des California Institute of Technology zahlen mussten, um ihn nach Saudi-Arabien zu bringen ? "usw.) .

Rückblickend verstehe ich, dass ich Saul daran interessieren möchte, einige der mathematischen Probleme zu lösen, die in meiner Arbeit aufgeworfen wurden. Ich glaube, ich habe immer noch nicht verstanden, inwieweit er die von anderen vorgeschlagenen Probleme gerne lösen wollte. Trotz eines bedeutenden Beitrags zur Entwicklung der Infrastruktur der Computerwelt hat Sol selbst Computer nie ernsthaft benutzt. Er war sehr stolz darauf, dass er in seinem Kopf leicht Berechnungen durchführen konnte. Bis zum Alter von 70 Jahren benutzte er keine E-Mail und benutzte zu Hause nie einen Computer, obwohl er ein Mobiltelefon hatte (er erhielt praktisch keine reguläre E-Mail. Ich erwähnte einmal, dass ich vor ungefähr einem Jahr die Geschichte von Ada Lovelace studierte ; er antwortete: "Die Geschichte von Ada Lovelace als Babbage-Programmiererin ist so weit verbreitet, dass jeder sie als Tatsache zu akzeptieren scheint, aber ich habe noch nie Quellen zu diesem Thema gesehen. ").

Sauls Töchter organisierten vor einigen Jahren eine Party zu seinem 80. Geburtstag und schufen so interessante Einladungen:



Saul hatte bestimmte gesundheitliche Probleme, obwohl es den Anschein hatte, dass dies seinen Lebensrhythmus nicht wirklich beeinträchtigte. Die Gesundheit seiner Frau verschlechterte sich und die letzten Wochen ziemlich scharf. Das Sol am Freitag , wie üblich, ging in sein Büro, und am Samstagabend starb er im Schlaf. seine Frau Bo überlebte ihn für zwei Wochen und starb nur zwei Tage vor dem 60. Jahrestag ihrer Hochzeit.

während Saul und links, sein Arbeitsleben in octillion Bits in der digitalen Welt.

P oschay, Saul und alle von uns -. Dank.

Jetzt auch beliebt: