ステーションX, 2000-04-02

偶然、以下の番組を見ましたが、英国の第二次大戦中の暗号解読に当たっていた「ステーションX」についてのドキュメントでした。ここで上げられるチューリングは昨年のタイム誌の20世紀特集で世紀の10人の科学者の1名に上げられていました。かなり不幸な死に方をされたのですが。
最近、話題になりつつある諜報組織エシェロンは、Station Xの後継的組織に思えます。


00-04-02（日）BSドキュメンタリー 11:00-11:50
Station X 英国軍の暗号解読情報作戦 (1998年英国の放送局が番組作成）
北アフリカの独軍にイタリーから物資を補給する艦船が、航空機で次々と轟沈されたが、独軍の暗号エニグマをステーションXで解読していたためである。
ドイツ軍にエニグマ解読を察知されないようにするためを、英軍は事前にわざと偵察機を飛ばして偵察機が発見したと思わせた。
ロンメル将軍は、イタリー側から情報が流れたと疑っていた（ノンメルの息子のインタビュー）。
1941年には、チャーチルはまだ参戦していなかった米国に情報を公開して、エニグマの秘密を米国に渡していた。
米国のカイロ大使館の暗号票が８月に独に盗まれて、ロンメルは１７日、英軍を480kmを後退させることに成功した。
エニグマの暗号解読にはアラン・チューリングが貢献し、ボンブを開発したた。
ローターに最初にコードを設定するが、独側はエニグマが解読できないと信じていたのでハイルヒットラーといった簡単なコードを与える場合があった。
最初のコードを探しあてるのに時間がかかったが、機械にエニグマの設定コードを解読できるホ゛ンブを開発、１０数分でボンブで解読することができ、ドラム→２０通り/秒で解読、数学的テクニックで可能性のないものを排除する。
一時は200台のボンブで暗号解読をした。
チャーチルは、北アフリカの戦いを重要視しモンゴメリーを投入、9/30、アラムハルパの戦い。モンゴメリーはStation Xの力を信頼していなかった。 英国はエルアラメインの戦いで大勝利したがロンメルはヒットラーに1942年11/2の夜に使える戦車は10数台しかない退却の願いを出したが、機甲部隊にヒットラーは引くなと命令したがロンメルは逃げた。本当はモンゴメリーは、ロンメルを捕まえることができたはずだが何故にげさせたかstationXは理解できない。
Station Xはロンドン近郊にブレンチェリー・パーク、Bletchley Parkに置かれ、1943年には人員は1万人に達した。米国人の派遣は５人であった。
エニグマの解読で1940年に初めて、英国内から送信しているスパイを捕まえることができた。エニグマを超える暗号機、謎の暗号機をヒットラーは自分専用として、テレプリンターを使用するものを、ローレンツというものを開発、１２枚、文字の配列、擬似乱数を出し、発信・受信でカモフラージュ用の文字を、それぞれに文字に入れるものだった。
機械だから、無意味ではない乱数を発生することはできない。
1941年8月に独側がミスをして、４０００字の暗号送付に読めないとの催促で、同じ４０００文字を同じ設定のカモフラージュをつけくわえるという大ミスをして、これはヒットラーと、最高司令部との連絡であったが、３ヶ月で解読した。それでも、その日の設定を解読するのはタニーという装置でも何週間もかかるの、スピードをあげることが課題となった。
暗号解読の機械は、トミー・フラワーズが開発した。真空管が1500個、使用されたものである。当時は150個でも大きいと思われており,驚くべき数であった。1943.3に機械造りをスタートしてコロッサス(Colossus)という装置を開発した。数分でローレンツを解読できる。テープの解読スピードをどんどん上げる。
ステーションXは、1944.6月のノルマンジー上陸作戦においてロンメルの通信を全て解読していた。6/4に前進を開始したが、悪天候で１日延長、6/6火に作戦開始、独国軍は半数は北部に。ステーションＸは足留め、独軍の62中、60個師団の場所を知る。デーニッツが降伏した。
戦後３０年間、Station Xの存在は秘密であった。チャーチルは隠して、ソ連の暗号を解読していた。戦後、コロッサスは破棄、埋めた。トミーフラワーズは書類を自ら燃やし、研究所に戻る。プログラム可能なコンピュータであった。情報組織にいくものもいた。
チューリングは1954年自殺した。グレッチェリーパークには偉大な人々がいた。ここで米国と英国の関係が生まれた。戦争の期間を２年短くした。多くの人命を救った。

Alan Mathison Turing （1912―54）
イギリスの数学者。ロンドンに生まれ、ケンブリッジ大学キングス・カレッジに学ぶ。1936年、計算可能関数の数学的定式化として思考上の計算機械を創案した。これは次のようなもので、彼の名をとって「チューリング機械」とよばれている。〔１〕限りなく大きな紙をもっている、〔２〕有限個の記号を用いる、〔３〕おのおのの瞬間に有限個のものを読み取る、〔４〕記憶の状態が有限個あり、各瞬間にどれか一つの状態にある、〔５〕現在みているものが何であり、状態が何であるかによって、次に何を消し、何を書き加え、どこに目を移すか、さらに次の状態が何であるかが決まる。関数が計算可能とは、その関数を計算するチューリング機械をつくることができることであり、この機械によって計算可能な関数は帰納的な関数と同じである。〈西村敏男〉

March 29, 1999 Time 100 Special Issue, vol.153,No.12
SCIENTISTS & THINKERS OF THE 20TH CENTURY

Computer Scientist
Alan Truring by Paul Gray
Born June 23, 1912 in London
1931-5 Studies mathematical logic at Cambridge
1937 Landmark paper introduces the imaginary Turing machine
1939-45 Secret work with team breaking the Nazis' Enigma codes
1950 Paper in journal Mind predicts the advent of artificial intelligence
1952 Convicted of gross indecency for homosexual acts
1954 Suicide, age 41

While addressing a problem in the arcane field of mathematical logic, he imagined a machine that could mimic human reasoning. Sound familiar?
<TURING WAS ENLISTED TO CRACK HITLER'S SECRET "ENIGMA" CODES>
At 13 he enrolled at the Sherbourne School in Dorset and there showed a flair for mathematics, even if his papers were critisized for being "dirty," i.e., messy. Turing recognized his homosexuality while at Sherbourne and fell in love, albeit undeclared, with another boy at the school, who suddenly died of bovine tuberculosis. This loss shattered Turing's religious faith and led him into atheism and the conviction that all phenomena must have materialistic explanations. There was no soul in the machine nor any mind behind a brain. But how, then, did thought and consciousness arise? After twice failing to win a fellowship at the University of Cambridge's Trinity College, a lodestar at the time for mathe-maticians from around the world, Turing rcceived a fellowship from King's College, Cambridge.
King's, under the guidance of such luminaries as John Maynard Keynes and E.M. Forster, provided a remarkably free and tolerant environment for Turing, who thrived there even though he was not considered quite elegant enough to be initiated into King's inner circles, When he completed his degree requiremcuts, Turing was invited to remain at King's as a tutor. And there he might happily have stayed, pottering about with problems in mathematical logic, had not his invention of the Turing machine and World War II intervened. Turing, on the basis of his published work, was recruited to serve in the Government Code and Cypher Schoo], located in a Victorian mansion called Bletchley Park in Buckinghamshire. The task of all those so assembled-mathematicians, chess champions, Egyptologists, whoever might have something to contribute about the possiblc permutations of formal systems-was to break the Enigma codes used by the Nazis in communications between headquarters and troops.
Because of secrecy restrictions,Turing's role in this enterprise was not acknowledged until long after his death. And like the invention of the computer, the work done by the Bletchley Park crew was very much a team effort. But it is now known that Turing played a crucial role in designing a primitive, computer-like machine that could decipher at high speed Nazi codes to U-boats in the North Atlantic. After the war, Turing returned to Cambridge, hoping to pick up the quiet academic life he had intended. But the newly created mathematics division of the British National Physical Laboratory offered him the opportunity to create an actual Turing machine, the ACE or Automutic Computing Engine, and Turing accepted. What he discovered,unfortunately, was that the emergency spirit that had sbort-circuited so many problems at Bletchley Park during the war had dissipated, Bureaucracy, red tape and interminable delays once again were the order of the day.
Finding most of his suggestions dismisscd, ignored or overruled, Turing eventually left the NPL for another stay at Cambridgc and then acceptcd an offer from the University of Manchester where another computer was being constructod along the lines he had suggested back in 1937.
Since his original paper, Turing had considerably broadened his thoughts on thinking machines. He now proposed the idea that a machine cuu]d learn from and thus modify its own instructions. In a famous 1950 article in the British philosophioal journal Mind, Turing proposed what he called an "imitation test," later called the "Turing test." Imagine an interrogator in a closed room hooked up in some manner with two subjects, one human and the other a computer. If the questioner cannot determine by the responscs to queries posed to them which is the human and whioh the oomputer, then the computer can be said to be "thinking" as well as the human. Turing remains a hero to proponents of artificial intelligence in part because of his blithe assumption of a rosy future: "One day ladies will take their computers for walks in the park and tell each other, My little computer said such a funny thing this morning!"
Unfortunatelly reality caught up with Turing well before his vision would, if ever, berealized. In Manchester, he told police investigating a robbery at his house that he was having "an affair" with a man who was probably known to the burglar. Always frank about his sexual orientation, Turing this time got himself into real trouble. Homosexual relations were still a felony in Britain, and Turing was tried and convicted of "gross indecency" in 1952. He was spared prison but subjected to injections of female hormones intended to dampen his lust. "I'm growing breasts!" Turing told a friend. On June 7, 1954, he committed suicide by eating an apple laced with eyanide. He was 41.

Who built the first computer?
<Mauchly;Paid a fateful five-day visit to Atanasoff>
<Eniac; The original room-size computer UNVEILED IN '46>
If you look at most history books, they'll tell you ENIAC (for Electronic Numerical Integrator and Computer) was the first true all-purpose electric computer.
Unveiled in 1946 in a blaze of publicity, it was a monstrous 30-ton machine, as big as two semis and filled with enough vacuum tube (19,000), switches (6,000) and blinking lights to require an army of attendants. Capable of adding 5,000 numbers in a second, a then unheard of feat, it could compute the trajectory of an artillery shell well before it landed (compared with days of labored hand calculations).
But while this electronic brain, as headline writers called it, took the spotlight, ENIAC had a lot of unsung rivals, many of them shrouded in wartime secrecy. At Bletchley Park, Alan Turing built a succession of vacuum-tube machines called Colossus that made mincemeat of Hitler's Enigma codes. At Harvard, large, clattering electromechanical computers in IBM's Mark series also did wartime calculations. Even the Germans made a stab at computing with Konrad Zuse's Z electromechanical computers, the last of which was the first general-purpose computer controlled by a program. For years, Eniac's principle creators, the late John Mauchly and J.Presper Eckert, held the unchallanged title of inventors of the modern computer-until an obscure physicist named John Atanasoff came forth to dispute their claims. In the late 1930s, while teaching at Iowa State College, he and a graduate student named Clifford Bell begun building a device that would allow them to solve large linear algebraic equation.
Their machine,later called ABC (for Atanasoff Berry computer), incorporated a number of novel features, including the separation of data processing from memory, and relied on binary numbers instead of ENIAC'S clumsier decimal arithemetic. But Atanasoff was called away in 1942 to work for Navy. Iowa State never filed for patents, and ABC was left abandoned in a storeroom.
But not entirely forgotten. In the late 1960s, Sperry Rand, which held the rights to Eckerts and mauchly's original Univac patents, sued Honeywell(which, like IBM, had got into the computer business) for royalty payments.
At one point in the six-year litugation, Atanasoff testified that Mauchly cribbed ABC's key features during a five-day visit in 1941. Mauchly indiguantly denied the aceusation. But the judge took a different view, In a 1973 decision that was never appealed, he invalidated Eckert and Mauchly's patents and in effect declared Atanasoff the winner. Hisiorians however, interpret the ruling more broadly, viewing it as an effort to keep competition alive in a fast-growing,industry. So who did invent, the computer? Novel as it may have been,ABC could not be reprogrammed, did not handle large numbers well and never became fully operational. By contrast, the reprogrammable ENIAC did initial calculations for the H-bomb, kept flashing away for nearly a decade and led to a host of more sophisticated successors. Take your pick. By Frederic Golden

チューリング機械　ちゅーりんぐきかい
イギリスの数学者チューリングA. Turingが考えた、思考のうえでの計算機械である。これは、現在のコンピュータの理論的な原型であるともいえる。計算の理論を展開するための思考上の機械であるから、現実のコンピュータのように計算時間を短縮するための機構や結果を見やすくするためのプリンターなどはついていない。理論を展開するのに必要な最小限の部品しかついていない。
　チューリング機械は、〔１〕無限に長いテープ、〔２〕ヘッド、〔３〕制御部、の三つの部分だけから成り立っている。テープには、情報を格納することのできる区分があり、一つの区分の中に一つの記号を書き込むことができる。そしてこのテープは、左右の方向に無限に延びている。ヘッドは、テープの一つの区分に書かれている記号を読み取ったり、書き換えたりする。制御部は、ヘッドとの情報のやり取りをしたり、ヘッドの位置を動かしたりする部分である。制御部は、有限個の状態をもちうる。ヘッドで読み取った記号と、制御部の状態により、次に機械がなすべき動作が決まる。機械の動作の仕様は、次のような規則をいくつか書き並べて表すことにしている。「状態ｑのとき、ヘッドがテープから記号ａを読み取ったら、ｚという作業をして、状態ｒへ移る」。
ここでｚには、次の3種類がある。(1)現在ヘッドがあるところのテープの区分の中にｂという記号を書く（読み取った記号ａは失われる）。(2)現在のヘッドの位置を右へ一区分だけ動かす。(3)現在のヘッドの位置を左へ一区分だけ動かす。テープに書き込んだり読み取ったりすることのできる記号は、有限個の種類しかないものとする。また、とりうる状態も、動作の仕様の規則も有限個に限る。このような機械に対して、次の四つを指定すると、この機械の動作が決まる。〔１〕利用するすべての記号、〔２〕とりうる状態、〔３〕この機械が始めにとる状態、〔４〕動作の仕様（規則の集まり）。
　チューリング機械は現実のコンピュータに比べると非常に簡単なものであるが、チューリングは、「ある問題を解くアルゴリズムが存在するということは、その問題がこの機械で解けることである」と定義した。アルゴリズムの存在の概念は、チューリングのほかに、クリーニStephen Cole Kleene（1909―　）、ゲーデルK. Goedelや、チャーチAlonzo Church（1903―　）、ポストEmil Leon Post（1897―1954）などが別々に考えていたが、のちになって、どれも同値の定義であったことが示された。チューリング機械の考え方は、現在のコンピュータ科学にとって重要な成果をもたらした。とくに、「チューリング機械で解けない問題が存在する」ことが証明されて、「アルゴリズムが存在しない問題がある」ことが明らかになった。つまり、このことはコンピュータに解けない問題があることを示している。
　あるチューリング機械の仕様をテープに書いておけば、その仕様の機械と同じ動きをするチューリング機械を万能チューリング機械という。これは、現在のプログラム内蔵方式のコンピュータと本質的に同じものである。万能チューリング機械は、チューリングのほか、高橋秀俊、池野信一、Ｍ・ミンスキーなど多くの人たちによって、簡素な仕様のものがつくられている。アルゴリズム
〈中西正和〉
【本】小林孝次郎著『計算可能性入門』（1980・近代科学社）　▽Ｍ・ミンスキー著、金山裕訳『計算機の数学的理論』（1970・近代科学社）　▽相沢輝昭著『計算理論の基礎』（1970・文一総合出版）

アルゴリズム Algorithm
ある種の問題を解くための計算の手順、方法であって、かならず、その解が得られるようなものをアルゴリズムという。このことばは、9世紀アラビアの数学者アル・フワーリズミーに由来するといわれている。たとえば、二つの自然数の最大公約数を求める方法は、次のように書くことができる。〔１〕二つの数をａ、ｂと名づける。〔２〕ａをｂで割り、その余りをｒとする。〔３〕ｒが０ならば、計算は終わり、答えはｂである。〔４〕ｒが０でなければ、そのときのｂをあらためてａと名づけ、ｒをｂと名づけて、〔２〕の段階に戻る。以上のプロセスは、ユークリッドの互除法とよばれるもので、最大公約数を求めるアルゴリズムである。ある問題を解くためのアルゴリズムがわかっていれば、コンピュータにそのアルゴリズムを教えて、つまり、プログラムをつくりそれをインプットして解かせることができる。コンピュータの登場以来、いくつかのアルゴリズムが脚光を浴び、発見されてきた。方程式の根を有限桁(けた)だけ求めるためのニュートン法や、データを大きさの順に並べ替えるための種々のアルゴリズム、プログラム言語を機械語に変換するためのアルゴリズムなど、いろいろな分野のアルゴリズムがある。
　一方、アルゴリズムという概念を数学的に厳密に定義しようという試みは、チューリングA. Turingや、クリーニStephen Cole Kleene（1909―　）、ゲーデルK. GoedelおよびチャーチAlonzo Church（1903―　）などの数学者により別々の方法で行われた。現在、それらの試みはすべて同値であることが示され、アルゴリズムという漠然とした概念が明確にされた。その結果、アルゴリズムが存在しない問題、すなわち、コンピュータで解けない問題があることも明らかにされている。〈中西正和〉