ソロモン・ゴロム（1932-2016）を記念して：最大長とポリオミノの線形フィードバックを備えたシフトレジスタの作成者

スティーブン・ウルフラムの投稿「 ソロモン・ゴロム（1932–2016） 」の翻訳。

出版物の翻訳と準備にご協力いただいたPolina Sologubに感謝します。

---

内容

- 歴史の中で最も一般的に使用される数学アルゴリズム

- サウル・ゴロムとの出会い

- ソロモン・ゴロムの物語

- シフトレジスタ

- シフトレジスタの背景

- シフトレジスタによって生成されたシーケンスが必要な理由

「 まあ、これらのレジスタはどこにありますか？」

- 非線形フィードバックを備えたセルオートマトンおよびシフトレジスタ

- ポリオミノ

- ストーリーの残り

---

歴史上最も一般的に使用されている数学アルゴリズム

十億 。 10億 これは、携帯電話またはその他のデバイスが最大長の線形フィードバックを備えたシフトレジスタを使用してビットを生成した回数の非常に大まかな見積もりです。 これは歴史上最も使用されている数学的アルゴリズムだと思います。 著者はソロモンゴロムで 、5月1日に亡くなりました。



1967年に出版されたソロモンゴロムの本「レジスターシフトのシーケンス」の基礎は、1950年代の彼の作品でした。 そして、そのコンテンツは現代の各通信システムに存在します。 3G 、 LTE 、 Wi-Fi 、 Bluetooth、さらにはGPSの仕様を読むと、これらのシステムが送信データのエンコードに使用するシフトレジスタによって生成されたシーケンスを定義する多項式への参照が見つかります。 ソロモンゴロムは、これらの多項式を作成した人です。



さらに、彼はレーダーを使用して金星までの距離を計算したり、火星から送信するための画像エンコーディングを開発したりする上で重要な役割を果たしました。 彼はポリオミノと呼ばれるものを世界に紹介しました（後にテトリスのクリエイター、「テトロミノテニス」に影響を与えました）。 彼は数え切れないほどの数学のパズルと駄洒落を作成して解決しました。 約20年前、私は彼が生まれたばかりの1959年にセルオートマトンに関する私のお気に入りのルール30の発見に非常に近いことを知りました。

サウル・ゴロムとの出会い

私は、私の専門的なつながりを通して、私が知っているほとんどすべての科学者と数学者を学びました。 しかし、ソラ・ゴロンバはそうではありません。 それは1981年で、21歳の物理学者（私は最初の授賞式でマッカーサー賞の最年少受賞者だったのでメディアで少し知られるようになりました）は、 カリフォルニア工科大学で研究していました。 私のオフィスのドアにノックがあり、若い女性がすぐにしきい値を超えました。 高エネルギーの理論物理学に従事していた当時は、絶望的に女性はほとんどいなかったため、これはすでに珍しいことでした。 私はカリフォルニアに数年間住んでいましたが、それでも私は大学を離れなかったので、私のオフィスに突入した南カリフォルニアのエネルギーの急増に備えていませんでした。 女性はアストリッドに自己紹介をし、オックスフォードを訪れていて、私が幼稚園にいた人を知っていると言いました。 彼女は、パサデナ地域の興味深い人々に関する情報の収集を任されていると説明しました。 彼女は私を難しい事件だと思っていたが、それでも会話を主張した。 かつて、私がやっていることについて何かを話そうとしたとき、彼女は言った。「 あなたは父と会わなければならない。彼はすでに老人だが、彼の心はかみそりのように鋭い 。」 偶然、Sol Golombの長女であるAstrid Golombが彼を紹介してくれました。



ゴロム家はパサデナ近くの山にある家に住んでいました。 彼らには2人の娘がいました：アストリッド-私より少し年上で、野心的なハリウッドの女の子、ベアトリス-私の年齢と科学的なメンタリティについて。 ゴロムの姉妹はしばしばパーティーを開きました-通常は自宅で。 テーマは異なっていました：ガーデンパーティーとフラミンゴとハリネズミを使ったクロケット（「 勝者は指定されたテーマに最も一致するコスチュームを持つ人 」）、またはルーンによって書かれた指示のあるストーンヘンジスタイルのパーティーです。 これらの政党では、地元のさまざまな著名人を含む若者やそれほど多くの人々が横断しました。 そして、彼らの少し側には、いつも大きなひげを持つ小さな男、エルフのような小さな男がいて、いつも暗いコートを着ていました-ソロモン・ゴロム自身。



徐々に、彼について少し学びました。 彼が「 情報理論 」に関与していたこと。 彼が南カリフォルニア大学で働いたこと。 彼はさまざまなあいまいであるが、明らかに高レベルの政府と他の関係を持っている。 私はシフトレジスターについて聞いたが、それらについてほとんど何も知らなかった。



1982年の秋、私はニュージャージー州のベル研究所を訪問し、セルラオートマトンの分野での最新の結果についてプレゼンテーションを行いました。 私が議論したトピックの1つは、 「加算的」（または「線形」）、セルオートマトン 、および限られた数のセルでの動作です。 セルオートマトンのセル数が限られている場合、その動作は最終的には必然的に繰り返されます...しかし、サイズが増加すると、最大繰り返し期間は、たとえば、追加のセルオートマトンのルール90の場合、完全にランダムな方法でジャンプします：1 、1、3、2、7、1、7、6、31、4、63、...しかし、パフォーマンスの数日前に、これらの期間が単純な要因またはセルの数に依存する式に従うように見えることに気付きました。 しかし、私がこれについて言及したとき、座っている人の一人が手を挙げて尋ねました。 「私の実験では、この数字を扱っていなかったので、知りませんでした。しかし、なぜ誰かが私にこれについて尋ねたのですか？



私に尋ねたのはアンドリュー・オドリジコと呼ばれていました -彼はベル研究所の理論家でした。 私は彼に尋ねた：「 何か特別なものがn = 37でつながると思うのはなぜですか？ 」 「 まあ 」と彼は言いました、「 あなたがしていることは線形フィードバックシフトレジスタ理論に関連していると思います 」と彼はソル・ゴロンブの本を見ることを提案しました。 「 ああ、はい 」と言いました、「 私は彼の娘を知っています... 」。 Andrewは正しかった。線形フィードバックシフトレジスタ用に開発されたSol理論に似た、多項式に基づく加算セルオートマトンの非常にエレガントな理論があります。 アンドリューと私はこれについてよく引用された記事を書いた（これは従来の数学的方法でセルオートマトンの振る舞いを説明できる稀なケースである）。 私にとって、副作用は、ソロモンゴロムが何をしたかについて何かを学んだということでした（覚えているなら、それはすべてインターネットの出現前でした）。

ソロモン・ゴロムの物語

ソロモン・ゴロムは1932年にメリーランド州ボルチモアで生まれました。 彼の家族はリトアニア出身でした。 彼の祖父はラビでした、そして、彼の父はまだアメリカに移り、数学の修士号を取得し、その後中世のユダヤ哲学に入り、ラビにもなりました。 ソルの母親は、ロシアの有名な家族の出身で、皇帝の軍隊のためにブーツを作り、銀行を率いていました。 ソルは学校で優秀であり、議論の最強でした。 父に触発されて、彼は数学に興味を持ち、17歳のときに素数に関する記事を発表しました。 高校を卒業した後、彼は数学を勉強するためにジョンズ・ホプキンス大学に入学し、ユダヤ人の学生のクォータにほぼ落ちました（したがって、彼は医学に行かないと約束しなければなりませんでした。通常の研究期間の半分の1951年）。



そこから、彼はハーバード大学に数学の大学院に行きました。 しかし、その前は、1912年に設立された航空宇宙会社であるGlenn L. Martin Companyで夏に働いていました。1920年代にロサンゼルスからボルチモアに移り、防衛請負業者となり、最終的にロッキードマーティンになりました。 ハーバード大学で、ソルは数論に特化しており、特に素数の集合の特性化に特化しています。 しかし、彼は毎年夏にマーティン社に戻りました。 彼が後にハーバードで言ったように、「 実用的なアプリケーションに彼らが教え、学んだことがあるかどうかという問題は、議論することはもちろんのこと、大声で言うことさえ不可能でした 。」 しかし、Martin Companyで、彼は知っていた純粋な数学-素数でさえ-シフトレジスタを含む実際の応用があることを発見しました。



Martin Companyでの最初の夏、Solは経営理論グループに割り当てられました。 第二の夏に、彼はコミュニケーション研究グループに入れられました。 そして1954年6月に、彼の上司が会議に出席し、そこで線形シフトでレジスタシフトの奇妙な振る舞いを聞いたことがあり、サウルにこの研究を行うことができるかどうか尋ねました。 すぐに、ソルは、有限体上の多項式の助けを借りてこのトピックを調査できることに気付きました。 翌年、彼はハーバード大学大学院とマーティンカンパニーのコンサルティングに時間を分け、1955年6月にシフトレジスタ理論の基礎となった最終報告書「 ランダムプロパティを持つシーケンス 」を執筆しました。



ソルは数学パズルが大好きで、チェス盤にドミノタイルを並べてパズルを熟考しながら、後に「 ポリオミノ 」と呼ぶものを発明しました 。 彼は1953年11月にハーバード数学クラブでそれらについてプレゼンテーションを行い、それらについての記事（彼の最初の研究作業）を発表し、それらと協力してハーバード数学賞を受賞しました。







1955年6月、ソルはフルブライトフェローシッププログラムでオスロ大学に 1年間留学しました。一部は著名な理論家と協力し、一部はノルウェー語、スウェーデン語、デンマーク語を学び（ルーン写本を学び）、コレクションを埋めました。言語スキル。 オスロでの滞在中、彼は素数に関する長い記事を完成させ、スカンジナビアを旅することに成功しました。デンマークでボーと名付けられた若い女性に会いました-彼女は大家族からであり、泥炭地だけで知られる田舎で生まれました苔ですが、なんとか大学に行き、哲学を学びました。 ソルとボーは仲良くなり、数ヶ月後に結婚しました。



彼らが1956年7月に米国に戻ったとき、サウルはいくつかのインタビューを行った後、カリフォルニア工科大学から分離され、軍事開発に従事していたジェット推進研究所であるJPLで働きました。 ソルは、上級研究エンジニアとしてコミュニケーションチームに含まれていました。 これは、研究室の人々が衛星を打ち上げる準備ができたときでした。 しかし、政府は軍事行動のように見えることを恐れて、彼らを許可しませんでした。 1957年10月、ソビエト連邦が国際地球物理学年の一環として衛星を打ち上げたときにすべてが変更されました。 驚くべきことに、米国はExplorer-1を立ち上げるのにたった3か月しかかかりませんでした。 JPLは衛星を打ち上げるために多くのことを行い、Solグループ（技術専門家が電子形式のレジスタシフトの実装に取り​​組んでいた）が放射線検出器を作成するために派遣されました。 この仕事中、ソルはハーバード大学に戻り、最終的な博士号試験に合格することができました。



それはJPLと宇宙計画に集中した時代でした。 1958年5月、Solが率いる新しい情報処理グループが形成され、同じ月に彼の最初の子供であるAstridが生まれました。 ソルは、耐妨害ロケットのシフトレジスタによって生成されるシーケンスの研究を続けました。 1959年5月、ソルの次の娘が登場し、ベアトリスと名付けられました（良い順序：A、B ...）。 1959年の秋、ソルはMITで学業休暇を取り、そこでクロードシャノンや他の多くのMIT著名人と出会い、情報理論と代数的コードの理論を研究しました。



当時、彼はすでに生物学の分野でコーディング理論の研究をしていた。 DNAのデジタル性は1953年にジムワトソンとフランシスクリックによって発見されたという事実にもかかわらず、4つの可能性のある塩基対の配列が20アミノ酸を正確にどのようにエンコードするかはまだ明確ではありませんでした。 1956年、Watsonのカリフォルニア工科大学のポスドクの前顧問であるMaxDelbrückは 、この問題についてJet Propulsion Laboratoryと相談しました。 ソルと彼の同僚の2人は、フランシスクリックのアイデアを分析し、塩基対の重複トリプルがアミノ酸をエンコードできる「コンマフリーコード」を思い付きました。 分析により、この方法で正確に20個のアミノ酸をエンコードできることが示されました。 これは最も驚くべき説明の1つでした。 しかし、残念ながら、生物学は実際にはそのようには機能しません（生物学では、64の可能性のあるトリプルの一部が何も表さない単純なコーディングを使用しています）。



生物学に加えて、ソルは物理学も学びました。 シフトレジスタによって生成されたシーケンスは、レーダー（GPSで使用）を使用して範囲を計算するのに役立ちました。 また、ソルは金星までの距離を見つける責任者に任命されました。 そして、1961年の初めに太陽、金星、地球が最もうまく並んだとき、 モハーベ砂漠にある85フィートのゴールドストーン無線アンテナを使用したソルは、金星からレーダー信号を受信し、地球と金星の距離に関するデータを明らかにしました。そして地球と太陽。



Solが言語、コーディング、およびスペースに興味を持っていることを考えると、彼がエイリアンに興味を持つようになったことは驚くことではありません。 1961年に、彼は「 地球外言語学への短いガイド 」と題する空軍の記事を書き、今後数年にわたって、このテーマに関する幅広い読者向けの記事をいくつか書いた。 彼は、 「エイリアンとの接触に関して、2つの主な問題があります。それらの1つは、相互に受け入れられるチャネルを見つける問題です。 もう一つは、より哲学的な問題（意味論的、倫理的、形而上学的）であり、議論のための適切な主題を見つけることから成ります。 簡単に言えば、最初に共通言語を見つける必要があり、次に何を言うかを考える必要があります 。」 彼は特徴的なユーモアを続けました。「 当然、彼らが十分な高貴な意図を持っているかどうかを知るまで、彼らに伝えすぎてはなりません。政府は間違いなく宇宙情報機関（KRU）を作成し、地球外の情報を監視します。 。かつて言ったように、安全HGウェルズは、 [または、それはのエピソードだったトワイライトゾーン 「人類に奉仕するために、」私たちは知る必要があり、願い- ？]エイリアンが彼らの唯一の目標ことを率直に言って私たちに教えてくれる場合でも、ということ 彼らは焼いたり揚げで私たちを提供しています。」



JPL Labで教えている間、Solは近くの大学（カリフォルニア工科大学、南カリフォルニア大学、 ロサンゼルス大学）でも教えていました。 1962年の秋、研究室の状況を変えた後（そしておそらく幼い子供たちともっと時間を過ごしたいと思ったため）、彼はフルタイムの教授になることを決めました。 彼は3つすべての大学からオファーを受けました。 彼は自由に仕事ができるところに行きたかった。 彼はカリフォルニア工科大学で「 ノーベル賞受賞者以外に影響力がない 」と言われ、ロサンゼルスでは「 誰も影響を与えられないような官僚制度がある 」と語った 。 その結果、ソルは評判が低いにもかかわらず、南カリフォルニア大学を選びました。 1963年の春に、彼は電気工学の教授として働き始め、最終的に53年間そこで働きました。

シフトレジスタ

サウルの人生の話を続ける前に、線形フィードバックシフトレジスタ（LFSR）とは何かを説明しなければなりません。 基本的な考え方は非常に簡単です。 それぞれが1または0（たとえば、黒または白）を含む一連の正方形を想像してください。 純粋なシフトレジスタでは、発生するすべてがすべての値を1ステップ左にシフトし、左端の値が失われ、新しい値が右に移動します。 フィードバックシフトレジスタの概念は、シフトレジスタ内の他の位置の値に応じて、シフトされる値が決定（または「フィードバック」）されることです。 フィードバック付きのリニアシフトレジスタでは、レジスタの特定の位置にある「ブランチ」からの値が2を法として結合されるため（2ではなく1 = 1 = 0）、XOR（「 排他的または 」）が適用されます。







しばらくすると次のようになります。







ご覧のとおり、シフトレジスタは常にビットを左にシフトし、他のビットは単純な規則に従って右に追加されます。 ビットのシーケンスはランダムに見えますが、図に示すように、最終的に繰り返されます。 ソルゴロンブは、そのようなシーケンスとその繰り返しを分析するためのエレガントな数学的な方法を見つけました。



シフトレジスタのサイズがnの場合、2 ^nの可能な状態（長さnのすべての可能なシーケンス0および1に対応）があります。 シフトレジスタの規則は決定論的であるため、特定の位置は常に異なる同じ位置に来る必要があります。 これは、ステップが繰り返される前にシフトレジスタが通過できるステップの最大数が2 ⁿであることを^{意味します} （実際、すべて0の位置は他に進化できないため、2 ⁿ -1）。



上記の例では、シフトレジスタのサイズは7であり、2 7-1 = 127ステップ後に正確に繰り返されます。 しかし、どのシフトレジスタ（どの分岐位置で）が最大長のシーケンスを生成しますか？ この質問は、ソロモンゴロムが1954年の夏に調査を開始しました。 そして彼の答えはシンプルでエレガントでした。



上記のシフトレジスタには、位置7、6、および1に分岐があります。ソルは、多項式x ⁷ + x ⁶ + 1を使用して代数的にこれを提示しました。 したがって、それを因数分解することはできません。これは、多項式間の素数の類似物になります。 そして、他のいくつかのプロパティの存在は、それを「 原始多項式 」にします。 今日、これはMathematicaシステムとWolfram言語を使用して簡単に検証できます：







その後、1954年、ソルはこのすべてを手動で行う必要がありました。 彼は、シフトレジスタに対応する原始多項式のかなり長いテーブルをコンパイルし、最大長のシーケンスを生成しました。

シフトレジスタの背景

デジタルパルスを送信する「 遅延線 」を通じてRAMを維持するという考えは、コンピューターの時代の始まりにまでさかのぼります。 1940年代の終わりまでに、このような遅延線は一連の真空管を使用してデジタル的に適用され、「 シフトレジスタ 」と呼ばれていました 。 最初のフィードバックシフトレジスタがいつ作成されたかは不明です。 おそらくこれは1940年代後半だったのでしょう。 ただし、このイベントは軍事暗号で最初に使用されたため、まだ謎に包まれています。



暗号化の主な考え方は、意味のあるメッセージを認識できないように変更することです。 ただし、キーがわかっている場合は、暗号化されたメッセージを再作成できます。 いわゆるストリーム暗号は、ランダム要素の長いシーケンスを作成するという原則に基づいて機能し、同じ要素シーケンスを独立して生成するレシーバーを使用してデコードされます。



線形フィードバックシフトレジスタは、長い繰り返し期間のために暗号法で評価されています。 ただし、Solがこれらの期間を見つけるために使用した数学的分析により、このようなシフトレジスタは安全な暗号化には適していないことが明らかになりました。 ただし、最初は非常に優れているように見えました（特にエニグマの連続したローターの位置と比較して）。 ソビエト軍の暗号システムがこれに基づいて構築されたというしつこい噂が広まりました。



2001年、私は私の著書A New Kind of Scienceの歴史的なメモに取り組んでいたとき、Solと私はレジスターシフトについて電話で長い間話しました。 サウルは、彼が始めたとき、シフトレジスタの暗号化作業について何も知らないと言った。 彼は、ベルの研究室、リンカーンの研究室、およびジェット推進の研究室のスタッフが、彼と同じ頃にシフトレジスタの作業を開始したと言いました。 しかし、彼は1955年の報告書で指摘したように、少し先に進むことができました。



その後の数年間、ソルは純粋数学に関する文献から彼の作品のさまざまな先駆者について徐々に学びました。 すでに1202年、 フィボナッチは、現在フィボナッチ数と呼ばれ、再帰関係（ゼロと1ではなく任意の整数で動作する線形フィードバックシフトレジスタの類似物と見なすことができる）によって生成されるものについて話しました。 0と1のサイクルに関する1900年代初期の小さな作品もありますが、最初の大規模な研究はオスロ大学のOusten Oreの作品でした。 Oreには、1940年代後半に国家安全保障局の前任者に助言したマーシャルホールという学生がいました。 -おそらくシフトレジスタの問題です。 しかし、彼がしたことはすべて分類されていたため、Solと線形フィードバックでシフトレジスタの履歴を公開するよう手配しました。 ソルは彼の本をマーシャルホールに捧げました。

シフトレジスタによって生成されたシーケンスが必要なのはなぜですか？

私は、単純なルールで定義されたシステムが多くのアプリケーションのバリエーションに終わることに何度も気付きました。 シフトレジスタもこのパターンに従います。 現代の機器とソフトウェアの両方にシフトレジスタが詰め込まれています。通常の携帯電話にはおそらく12個または2個あり、通常ハードウェアレベルで実装されます。つまり、線形フィードバックシフトレジスタ-LFSR）です。



ほとんどの場合、最大長のシーケンスを提供するシフトレジスタが使用されます（「 Mシーケンス 」とも呼ばれます ）。 それらが使用される理由は、通常、Solが発見したそれらの特性のいくつかに関連しています。 それらには常に同じ量の0と1が含まれます（実際には、常に1つだけ余分に1があります）。 続いて、Solは、同じ数のシーケンス00、01、10、および11によって、また大きなブロックについても特徴があることを示しました。 たとえば、入力としてビットのすべての可能な組み合わせをテストする場合、「 balance 」のこのプロパティは、それ自体ですでに非常に便利です。



しかし、Solはさらに重要な別のプロパティを見つけました。 シーケンスの各0を1に置き換え、シーケンスのシフトバージョンの各要素に元の対応する要素を乗算します。 ソルは、追加すると、これらの要素が常にゼロになることを示しました（シフトがない場合を除く）。 つまり、シーケンスは、それ自体のシフトされたバージョンと相関がありません。



これらのプロパティは、0と1の十分に長いランダムシーケンスに対して真になります。最大長のシーケンスに対してこれらのプロパティが常に真であることは驚くべきことです。 シーケンスにはランダム性がありますが、実際にはカオスではありません。 明確に組織された構造を持っています 。



この構造が線形フィードバックシフトレジスタの特徴であり、それらを深刻な暗号化に適さないものにします。 しかし、それらは基本的な「要素の再配置」と安価な暗号化に最適であり、これらの目的で積極的に使用されています。 多くの場合、タスクは単に信号を「ホワイトニング」することです（「ホワイトノイズ」のように）。 0. , «» . , . Wi-Fi , Bluetooth , USB , TV , . .



— , ( DVD 16 24 ; GSM ).



GPS . GPS , , 10 . , . , , ( GPS, 1024 ).







- . , , . — " ", , 1 ( ) . CRC ( ), , . , , , , — , - , .



, , . , , — , ( «Enable Spread Spectrum» BIOS).



— CDMA ( ). , «», . «» ? «» . ( TDMA — ). CDMA .



, , , ( ) , . , , . 3G .



, . 1959 , . , . , 1968 Linkabit , ( ).



1985 Qualcomm . , 1990- , CDMA , .

?

, , , . . , , (PN, , M-, FSR, LFSR , MLS, SRS, PRBS, . .).



, , , , — , . 2G TDMA, , , CRC ( ) . 3G — CDMA, , , . 4G , , CRC : , , . 5G — , . , , «-», ; , .



, . , , , — , CRC ( ) , , , . ( PCIe , SATA . .): , , HDMI . CRC , , , .



, , . 10 , — , IoT (« ») . ( !) — 10 .



? , « », , ( CDMA) . , — .



10 , 1/10 ( 3- ), 1 , , .



? そう思う。 , . , , . ? - .



« », , . (. " ( ) "), ( , , - , ). « », . ( " ", " " . .), , «» . , , , , ; , , , - .

これは一見して明らかではないように見えますが、フィードバック付きのシフトレジスタとセルオートマトンの間には密接な関係があることがわかりました。 フィードバックシフトレジスタの基本的な構成は、一度に1ビットを計算することです。 セルオートマトンには1行のセルがあり、各ステップで、すべてのセルは、たとえば、最近傍の値に依存するルールに基づいて並行して更新されます。



それらがどのように関係しているかを確認するには、サイズnのフィードバックでシフトレジスタを開始し、同時にnステップごとにのみステータスを表示する必要があります。 つまり、すべてのビットが再表示される前に上書きできるようにします。 線形フィードバック付きのシフトレジスタの各ステップが表示されている場合（ここでは2つのブランチ）、各ステップですべてが左にシフトします-それだけです。 ただし、圧縮された画像を作成し、 nステップごとに表示すると、パターンが表示されます。







これはネストされたパターンです。 この図は、セルオートマトンがセルとその隣接セルを取り、それらをモジュロ2（XOR）で加算した場合に取得できるものと非常に似ています。 これは、セルが上記のシフトレジスタと同じサイズの円になるようにセルを配置する場合に、セルオートマトンで発生することです。







最初は、セルオートマトンとシフトレジスタのパターンはまったく同じであることが判明しました。 これらの写真を見ると、シフトレジスタの数学がセルオートマトンに関連していることは驚くほどではありません。 そして、ネストされたパターンの再現性を考えると、なぜシフトレジスタのエレガントな数学理論が存在しなければならないかが明らかになります。



実際に使用される一般的なシフトレジスタの場合、このような明示的に繰り返されるパターンは特徴的ではありません。 最大長のシーケンスを生成するシフトレジスタの例を次に示します。 事実、枝は遠く離れているため、入れ子の視覚的な痕跡を見つけるのは困難です。







シフトレジスタとセルオートマトンの対応はどれくらい広いですか？ セルオートマトンの場合、新しいセル値を生成するためのルールは何でもかまいません。 線形フィードバックシフトレジスタでは、常にモジュロ2（またはXOR）加算に基づいている必要があります。 これが、「線形フィードバックシフトレジスタ」の「線形」部分の意味です。 また、任意のルールを使用して、シフトレジスタの値を非線形フィードバック（NFSR）と組み合わせることもできます。



実際、Solは線形フィードバックシフトレジスタの理論を開発したとき、非線形の場合から始めました。 1956年にJPLに到着したとき、彼は小さな電子モジュール用のラックを備えた実験室を受け取りました。 Saul氏によると、Bell Labsプロジェクトが特定の論理演算（AND、OR、NOT、...）を実行するために、モジュール（それぞれタバコパックのサイズ）が構築されたという。 モジュールを一緒に使用して、希望する非線形フィードバックシフトレジスタを実装し、1秒あたり約100万ビットを提供できます（ソルは、誰かがユニバ​​ーサルコンピューターを使用して同じことを試みたが、ハードウェアモジュール、ユニバーサルコンピューターでの作業に6週間かかりました）。



ソルが線形フィードバックでシフトレジスタの研究を始めたとき、彼の最初の深刻な発見は、それらの繰り返しの期間でした。 そして、非線形の場合、彼は同じことを理解しようとすることにほとんどの努力を向けました。 彼はあらゆる種類の実験データを収集しました。 彼は、1年かかった^2,445のシーケンスもチェックしたと言った。 下の図のように、彼は要約を作成しました（波形ラインに表示されるシーケンスの視覚化に注意してください）。 しかし、彼は線形シフトフィードバックレジスタに対して持っていた一般理論を思い付くことはありませんでした。







彼ができなかったのも不思議ではありません。 すでに1950年代に、理論的な結果が現れ（ほとんどの場合、 チューリングの普遍的な計算のアイデアに基づいています）、そのプログラムは原則としてこれを行うことができました。 Solや他の誰も、非常に単純な（非線形の）関数が非線形フィードバックのあるシフトレジスタで使用されるとは思わなかった。



そして、後になってようやく、非常に単純なプログラムの振る舞いがどれほど複雑になるかが明らかになりました。 私のお気に入りの例は、セルオートマトンのルール30です。この場合、隣接セルの値は、 p + q + r + q * r mod 2 （またはp XOR（ q OR r ） ）として表現できる関数を使用して結合されます。 信じられないほど、Solは同様の関数p + r + s + q * r + q * s + r * s mod 2に基づいた非線形フィードバックを持つシフトレジスタを検討しました。 以下に、Sol関数（ " 規則29070 "と考えることができる）、規則30、および他のいくつかの類似の規則がシフトレジスタでどのように見えるかを示します。







そしてここでは、セルラーオートマトンと同様に、固定サイズのレジスタに限定されません。







もちろん、Solはこのような写真を撮ったことはありません（1950年代にはほとんど不可能でした）。 代わりに、彼は一種の集約特性として繰り返し期間に焦点を当てました。



Saulは、非線形フィードバックを備えたシフトレジスタがランダム性の原因になるのではないかと考えました。 セルオートマトンについて今日知られていることから、彼らができることは明らかです。 たとえば、Mathematicaシステムのランダム性を作成するために、25年にわたって30個のセルオートマトンのルールを使用しました（数兆の可能性を研究することで発見したより効率的なルールを支持して最近それを放棄しましたが）。



ソルは暗号化について少し話した。 彼は政府のために長く働いていなかったと思うが。 彼は、1959年に「 非線形シーケンスに対する多次元相関攻撃 」を発見したが、 「 プログラムが暗号解読のためであるという主張を慎重に避けた 」 と言った 。 事実、セルラーオートマトンのルール30（および場合によっては非線形フィードバック付きのシフトレジスタ）は優れた暗号システムになる可能性がありますが、線形フィードバック付きのシフトレジスタと同等であると思われるという事実により（そうではありません） ）、可能な限り使用されたことはありません。



熱狂者として、過去数十年にわたって、私は1次元セルオートマトンに関する私の仕事のすべての前任者を研究しようとしました。 2次元セルオートマトンはほとんど研究されていませんが、1次元オートマトンの場合は、純粋に理論的な研究が1つだけ見つかりました。 私が見たすべてのことの中で、ソロモン・ゴロムの非線形フィードバックを備えたシフト・レジスターは、最終的に四半世紀後にやったことに最も近いと判明したと思います。

ポリオミノ

「 ゴロム 」という名前を聞くと、多くの人がシフトレジスタを思い出します。 しかし、ほとんどはポリオミノについて覚えています 。 ソルはポリオミノを発明しませんでしたが、彼は名前を作り出しました。 彼は、かつて個々のパズルにしか現れなかったものを体系的に作りました。



ソルが興味を持った主な質問は、ポリオミノセットがどのように組織化され、特定の領域をカバーできるかということでした。 時にはそれはかなり明白であり、時にはそれはかなり複雑です。 Solは1954年にポリオミノに関する最初の記事を公開しましたが、 Martin Gardnerは1957年にポリオミノを非常に人気にしました（ Scientific Americanの数学ゲームに関するコラムを書きました）。 ソルは1964年の彼の本の序文で説明したように、その結​​果、「 世界中から、あらゆる人生からの特派員の絶え間ない流れ：主要な大学の理事会の議長、有名な刑務所から投獄された未知の修道院の住民... 」



ゲーム会社も新しいパズルに注目し、数か月の間にタイトルが「 新しいセンセーショナルなパズル 」のようになり、その後ポリオミノに基づいた数十年のパズルやゲームが続きました（いいえ、邪悪なハゲ男はソルのようには見えません）：



















ソルは、最初の公開からさらに50年間、ポリオミノに関する記事を公開しました。 1961年に、彼はフラクタル（「無限タイル」）パターンを作成できる小さなパーツ「爬虫類」に分割するオプションを導入しました。 しかし、Solがpoliominoで行ったほぼすべての作業には、特定の問題の解決が含まれていました。



ポリオミノの詳細にはあまり興味がありません。 より一般的な性質の関連する現象に興味があります。 いくつかの単純な形式で飛行機全体を「橋渡し」できるかどうかを判断するのは簡単だと思われます。 しかし、ポリオミノの場合（およびそれらに基づくすべてのゲームとパズルの場合）、すべてがそれほど単純ではないことが明らかになります。 そして実際、1960年代には、このタスクが理論的に不溶性であることが証明されました。



限られた領域のみに関心がある場合、原則として、考えられるすべての図の配置をリストし、必要に応じて配置されているかどうかを確認できます。 しかし、無限に興味があるなら、これはできません。 たぶん、100万個を正常に配置するオプションを誰かが見つけるかもしれませんが、この結果をさらに配布できる保証はありません。



動作するチューリングマシンまたはセルラーオートマトンのように見えるかもしれません。 タイルのラインから始めます。 そして、無限のタイリングが可能かどうかの質問は、チューリングマシンのインストールが可能かどうかの質問と同等です。 事実、チューリングマシンがユニバーサル（つまり、可能な計算を実行するようにプログラムできる）である場合、その停止問題は解決できない可能性があります。つまり、タイルの問題も解決できないということです。



もちろん、これはフォームの元のセットに依存します。 問題は、普遍的な計算をコーディングし、タイリングの不溶性の問題を引き起こすために、フォームがどれほど複雑でなければならないかです。 ソロモンゴロムはこのトピックに関する文献を知っていましたが、特に興味はありませんでした。



洗練され慎重に設計されたpoliminoセットが実際にユニバーサルコンピューティングをサポートすることはよく知られています。 しかし、単純なセットはどうでしょうか？ 彼は偶然彼につまずくのに十分なほど単純ですか？ 私が研究したすべてのシステムを見ると、最も単純なセットは本当にシンプルであることがわかります。 しかし、見つけるのは難しいです。



はるかに簡単なタスクは、非周期的ではありますが、平面を正常に埋めるポリオミノを見つけることです。 ロジャーペンローズは1994年に 適切な例を 見つけました 。 私の本「 A New Kind of Science」では、 3つのポリオミノを使った少し単純な例を挙げました。

残りの話

サウルは、シフトレジスターとポリオミノの分野で顕著な成功を収めたとき、30歳強でした...彼は非常に活発な人でした。 彼は数百の記事を書きましたが、そのうちのいくつかは以前の研究を拡張し、いくつかは彼が尋ねられた質問への回答であり、いくつかはただの楽しみのために書かれたようです-数字、シーケンス、暗号システムなどについて興味深いことを見つけるためにd。



シフトレジスタとポリオミノは膨大なトピックです（ AMS分類では個別のカテゴリに分類されます）。 最近数十年で、彼らは彼らの基礎に基づいてコンピュータ実験を行い始めたとき、彼らは両方とも新しいラウンドの開発を受けました。 ソルも彼らに活躍しました。 ただし、多くの質問は未回答のままです。 そして、線形フィードバックを備えたシフトレジスタについて大きなアダマール行列を見つけることができる場合、非線形フィードバックを備えたシフトレジスタについてはほとんど知られていません。



ソルは常に、数学と単語の両方のパズルに興味を持っています。 しばらくの間、彼はLos Angeles Timesのパズルのコラムをリードし、32年間、ジョン・ホプキンスの同窓生誌で「 ゴロムガンビッツ 」を執筆しました。 彼はMegaIQのテストに参加し、彼と彼の上司が国内のトップ5に入ったときにホワイトハウスへの旅行に勝ちました。



彼は大学での仕事に多大な努力を注ぎました：彼は学生を教え、大学院生を導き、行政のはしご（大学評議会の議長、研究の副学長など）に登っただけでなく、大学全体の管理についても意見を述べました「教員に相談する：削除するか、辞めるか？」というタイトルの記事を書きました;回答：いいえ、これは大学に適しています！）。 南カリフォルニア大学で、彼はヘッドハンティングに従事し、そこでの仕事中に、大学が教育プログラムの評価のトップからトップに上がるのを助けました。



そして、コンサルティングがありました。 ソルは細心の注意を払い、政府機関のために何をしていたかを明らかにしませんでした。 60年代の終わりに、彼はポリオミノに基づいたゲームの販売に従事していたことに失望し、SolはRecreational Technology、Incという会社を設立しました。 物事はうまくいきませんでしたが、ソルは、理論とパズルのコーディングに熱心だったバークレーの教授、 アルビン・バーレカンプに会いました。 その後、 サイクロトミクス （ x ⁿ -1形式のサイクロトミック 多項式に敬意を表して）を設立し、最終的にコダックにラウンドサムとして売却しました（ベルレカンプもアルゴリズム取引システムを作成し、 ジムサイモンズに売却し、 ルネサンステクノロジーの出発点となりました-これまでで最大のヘッジファンドの1つ）。



10,000件以上の特許が何らかの形でサウルの仕事に関連していますが、ソル自身は準グループに基づく暗号システムの特許を1つしか受け取りませんでした。



長年にわたり、ソルはイスラエル工科大学のテクニオンと協力してきました。 彼は自分を「 非宗教的正統派ユダヤ人 」と言ったが、同時に創世記で初心者向けのセミナーを教えたり、死海の巻物（クムラン写本）の解読にも取り組んだことがある。



サウルと彼の妻はよく旅行しましたが、サウルの「世界の中心」は間違いなく南カリフォルニア大学のロサンゼルスにある彼のオフィスであり、彼と彼の妻が60年近く住んでいました。 彼はいつも友人や学生に囲まれていました。 そして彼には家族がいました。 彼の娘アストリッドは、 リチャードファインマン （彼女が彼のためにポーズをとった）についての演劇で、またキャラクターの1つとして友人の小説で、学生の役割を果たしました。 ベアトリスは、さまざまな種類の医学的適応と診断（湾岸戦争に関連する疾患、スタチン効果、しゃっくりの発作など）に数学レベルの精度を適用することに専念しました。 私は、後に彼女の夫になった男、現代計算神経科学の創始者の一人であるテリー・セイノフスキーに彼女を紹介することで、ベアトリスの人生に少し貢献しました。



ソルは多くの出来事に関与しているようでした。たとえ彼が詳細についてあまり広めなかったとしても。 私は時々彼と科学と数学について話したいと思っていましたが、彼は個人と組織の両方についての話（多くの場合非常に魅力的です）に興味がありました（ " 1985年に]会議で、 クロードシャノンは情報理論に関する年次会議のバーで警告なしに登場したばかりですか？ 「;」 サウジアラビアに行くためにカリフォルニア工科大学の校長にいくら払わなければならなかったか知っていますか？ ） 。



振り返ってみると、私の仕事で提起された数学的問題のいくつかを解決する上で、ソルに興味を持ちたいと思います。 私は、彼が他の人々によって提案された問題を解決するのが好きな程度をまだ理解していなかったと思います。 コンピューティングワールドインフラストラクチャの開発に大きく貢献しましたが、Sol自身はコンピューターを真剣に使用していませんでした。 彼は自分の頭の中で簡単に計算できることを非常に誇りに思っていました。 70歳まで、彼は携帯電話を持っていたが、自宅では電子メールを使用せず、コンピューターも使用しなかった（彼は実際に定期的な電子メールを受信しなかった。私は何年か前にAda Lovelaceの歴史を研究したと言った;彼は答えた：「 バベッジのプログラマーとしてのAda Lovelaceの話は非常に広まっているので、誰もがそれを事実として受け入れているように見えますが、私はこの主題に関する情報を見たことはありません。 」



数年前、サウルの娘たちは80歳の誕生日にパーティーを開催し、このような興味深い招待状を作成しました。







サウルには特定の健康上の問題がありましたが、これは彼の生活のリズムに実際には影響を与えなかったようです。 彼の妻の健康状態は悪化しており、過去数週間で非常に劇的に悪化しました。 金曜日、ソルはいつものように彼のオフィスに行き、土曜日の夜に彼は夢の中で亡くなりました。 彼の妻ボーは彼をわずか2週間で生き延び、結婚60周年のわずか2日前に亡くなりました。



ソルは去りましたが、彼の作品はデジタルの世界で10億ビットで生きています。



さようなら、ソル。 そして、私たち全員から-ありがとう。