予想外にチューリング完全なソフトウェア構成、言語、およびAPIのカタログ。 安全性と信頼性に対するこれの結果。 アプリケーション：コンピューターに何台のコンピューターがありますか？

かなり複雑なCまたはFortranプログラムには、Common Lisp言語の半分の、新しく作成された、不特定の、バグがあり、遅い実装が含まれています 。 -第10グリーンスパン規則

チューリング完全性 （TC）は、入力と出力のいくつかの単純な表現を備えた計算可能な関数を実装するシステムのプロパティです。

チューリングの完全性は、コンピューターサイエンスの基本概念です。 完璧なウイルス対策プログラムを作成できない理由など、多くの重要な質問に答えるのに役立ちます。 しかし同時に、それは驚くほど一般的な出来事です。 コンピュータシステムが、あらゆるプログラムを実行できるほどの普遍性を実現することは難しいように思えますが、逆は真実です。すぐに完全なチューリングにならない有用なシステムを書くことは困難です。 原則として、入力データを少しでも制御して結果に変換するだけでも、チューリング完全なシステムを作成できることがわかります。 面白くて便利（ 通常はそうではありません ）、有害または非常に安全ではない、ハッカーへの真の贈り物（ 「言語理論のセキュリティ」を参照してください。 「奇妙なマシン」のハッキング方法を研究しています¹ ） この動作の驚くべき例は、チューリングの完全性がどこにでも潜んでおり、システムを保護することは非常に難しいことを思い出させます。

あまりにも強力なプログラミング言語も、不快なDoS攻撃を引き起こす可能性があります。 Fazzer aflは、 OpenBSDで無限ループを生成できるroffを見つけ、文字列置換ルールを乱用しました。

おそらく、チューリング完全システムのこれらの予想外の例は、「発見された」または「発見された」 難解なプログラミング言語のサブセットとしてよりよく考えられます 。 したがって、非常に最小限のFRACTRANは考慮されません² 、特別に難読化された言語Malbolge （些細なプログラムを書くには何年もかかるでしょう）は、特別に設計された難解なYaPであるためです。 また、チューリングの完全性に関する質問がリリース直後に現れたため、 Lifeゲームはサブセットに含まれていません。チューリングの完全性の認識は驚きではありませんでした。 また、ルーティングとパケットスイッチングを使用したネットワークの複雑さを考えると、セルラーオートマトンをこれらのネットワーク上に構築したり、 ロジックスキームをプログラムしたりすることは驚くことではありません。チケットの計画/検証は、 NP困難であり、EXPSPACE困難なタスクであるだけでなく 、複雑な航空会社の規則）。

結局のところ、多くの構成、特殊言語、ツール、または複雑なゲームは、 MediaWiki 、 sed テンプレート、またはエディターでの繰り返し正規表現/検索-置換コマンドのように、 最小電力のルールに違反し、 「偶然チューリング完全になります」 。 一般に、任意の形式の行の置換やテンプレート、または高確率でのオンザフライのコンパイルは、しばしば難解な言語「 /// 」などのラムダ計算または言語またはラベルの用語の書き換えをサポートするため、チューリング完全なシステム自体または繰り返される場合です。またはthue 。

XSLT 、 無限掃海艇 、 ドワーフ 要塞 ³ 、Starcraft、 Minecraft 、 Ant 、 Transport Tycoon 、 C ++テンプレートおよびJavaの一般化 、 DNA計算など-これらはすべてチューリング完全なシステムであり、これも驚くべきことではありません。 多くのゲームは、開発およびカスタムMODを簡素化するスクリプトをサポートしています。 したがって、チューリング完全なゲームを基本にするには、構文を有効にして、Perlなどのより有名な言語を呼び出します。

チューリングの完全性は、単に標準形式のあまり知られていない部分かもしれません。 おそらく、私たちの時代には、多くの人がTrueTypeと多くのフォントがELFメタデータやDWARFデバッグ情報に似たスタックされたマシン上のPostScriptプログラムであることを知らないでしょう。 または、 一部の音楽形式はMIDIを超えており、スクリプトをサポートしており、解釈が必要です。 フォントのチューリング完全性に気づいている場合、Turing of TeXドキュメントの完全性はもはや驚くことではありません。これは、 BLENDまたはLinux SNESおよびNESエクスプロイトなど、フォントおよびメディアに多くの深刻で興味深いセキュリティ脆弱性を自然に引き起こします。 PDFなどの他の形式では、ひどい量の脆弱性があります⁴ 。 繰り返しますが、レゴブロックやドミノから小さなチューリングマシンを作成するなどの顕著な成果⁵ 機械式コンピューターがどのように機能するかを長い間知っているので、考慮されていません。

一方、奇妙なマシンと呼ばれる一連のコンピューターセキュリティ研究では、本当に驚くべきチューリング完全なシステムが明らかになります。 さらに、それらは異なる人々に異なる程度の驚きを引き起こします：他の人を驚かさない1つは珍しいようです。

• ペアノ算術 ：自然数の加算と乗算はチューリングの完全性に十分です。 それどころか、 プレスブルガー算術は乗算を欠いているため、チューリング完全ではありません。
• ヴァンタイル ：マルチカラーの正方形。その配置は、2つのタイルの隣接する辺が同じ色でなければならないというルールによって決定されます（ヴァンにとって歴史的に明らかですが、システムは私を驚かせ、おそらく他の多くの人々）。
• x86詐欺：
  
  • MMUは RAMをシャッフルしてプログラミングを簡素化します。 プログラムがメモリ内のアドレスを特別な方法で正しく割り当てると、コード自体を実行することなく、 ページ違反例外 （ コメント ; 科学的研究 ）を使用してMMUで任意の計算を実行できます。 MMU例外メカニズムは、1つの命令でコンピューターに変わります 。
  • movはチューリング完全なシステムです。CPUとRAM間でデータを転送する一見無害なアセンブラー命令movにより、 TTAトリガートランスポートアーキテクチャ上の1つの命令でコンピューターを実装できます。 そのようなコンピューターでは、 Doomをプレイできます（ボーナスとして： xor指示も）。
  • 「X86はレジスタのないチューリング完全セットです。」
• Return-into- libc攻撃：ソフトウェアライブラリは、あらかじめパッケージ化された機能を提供します。各機能は、1つの有用なことを行うように設計されています。 これらの関数の呼び出しから、セキュリティメカニズムをバイパスできるチューリング完全な「言語」を作成できます。これは、攻撃者が独自の認識可能なコードを実行しないためです。 他の多くの例の中で、 「骨の上の罪のない肉の幾何学：関数呼び出しのないreturn-into-libc（x86）」および「return-into-libc攻撃の表現力について」を参照してください 。
• ポケモンイエロー ： 「 ポケモンイエロー フルコントロールハック」は、ゲーム内のアイテムを前後に移動して購入することにより、ゲームボーイアセンブラ上で任意のプログラムを作成できるメモリ破損攻撃について説明しています。 speedran （スピードパッセージ）のファンによる同様の成果がありますが、通常は「汚れた」ものとして無視します。たとえば、SNESのスーパーマリオワールドを「Snakes」や「Pong」のような任意のゲームに変えることができますが、新しいプログラムを追加の機器にダウンロードする必要があります。 私の意見では、これはスーパーマリオワールドを「予期せぬ」チューリング完全なシステムと呼ぶことを許さず、この記事の他の例とは異なります。 たとえば、Super Game BoyからSNESおよびIRCなどの任意のコードに移動できます 。 これは議論の余地のある違いです。
  
  • 同様のメモリ破損の問題は、他のCライブラリ関数と同様に、POSIXのprintfの%nオプションで発生します（ Karlini et al。、2015 ）。 したがって、 printf « printbf -Brainfuck « printbf 。
  • StarCraftコミュニティは、ゲームのバッファーオーバーフローを利用して、複雑なマップ、防衛ゲーム、マリオゲーム、およびレベルエディターを実装しました。 SCの更新バージョンでMODを保護するためにエミュレーションをハッキングすると、Blizzardに多くの問題が発生しました 。
• 組紐ゲームは完了しました
• その後の音符を転送するための指示を含む楽譜は、 Choonの 難解な言語となります。
• 心臓の筋肉細胞（心筋細胞）は、 論理ゲートを介してプログラムできるように相互作用するため、チューリング完全なシステムを表します （セルオートマトンは生物学的な例を使用して作成されるため、おそらく驚くことではありません ）
• ユーザーが機械的なスイッチをクリックするか、システムが次のステップに進むための唯一の可能な選択を行わなければならないため、奇妙なマシンの1つのカテゴリは完全なチューリング完全ではないと見なされます。 この場合、ユーザーはロジックを導入せず、計算も実行しないため、このカテゴリはチューリング完全システムの定義を完全には満たしません。
  
  • Magic：the Gathering ：これは、プレイヤーが提案されたオプションに機械的に同意するという仮定に基づいたチューリング完全なシステムですが、それ以外はすべてのアクションがゲームのルールに従います
  • CSSは 、HTMLページの視覚的外観をカスタマイズするための宣言型マークアップ言語として設計されていますが、ブラウザーでの機械的なマウスクリックによって状態を変更する基本的なセルオートマトンルール110は 、CSS宣言で エンコード できます。
  • ユーザーがアクティブなアニメーショントリガーをクリックすると、特別なリンクを持つMicrosoft PowerPointアニメーション（マクロ、VBScriptなどを除く）でチューリングマシンを実装できます（ Wildenhain、2017年 ： ビデオ ; PPT ）

おそらく、次のシステムは誤って完全にチューリングされます。

• クリックなしのCSS
• SVG：PostScriptは設計上TCですが、XMLで書かれた、つまり（通常）チューリング完全ではないドキュメント言語で書かれた、より現代的なSVGベクトルグラフィック形式はどうですか？ XSLTとの組み合わせではまだそうであるように思えますが、Webブラウザーの通常のコンテキストでは、この証拠や証拠は見つかりませんでした。 SVG標準は素晴らしく、時には恐ろしいものです。SVG1.2標準の失敗バージョンは、SVGイメージでネットワークソケットを開く機能を追加しようとしました。
• Unicode ： Nicholas Seriotは、アラビア語やヘブライ語などの右から左へのスクリプトを表示するように設計された双方向Unicodeアルゴリズムは 、大文字と小文字を区別するルール（トルコ語など）を介してタグシステムをサポートするのに十分複雑になる可能性があることを示唆しています

こちらもご覧ください

• プラットフォーム内効果

参照資料

• HNでのディスカッション： 1、2
• 偶然二次
• 「コーディングマシン」 ; 「信頼の委任に関する考察」ケン・トンプソン、1984
• 「ニューラルネットワークの敵対的再プログラミング」 、Elsayed et al。、2018

アプリ

コンピューターには何台のコンピューターがありますか？

奇妙な車や、AIエージェントが「大きく」なることについての論争で動揺する人もいます。そのような人、2人、10人、または数百万人が作成されます。 これは組織的な問題であるため、問題ではありません。 実際、システムの入力と出力は重要です。システム全体の効率と、消費するリソースはどれくらいですか？ Googleが50台のスーパーコンピューター、50,000台のメインフレーム、500万台のサーバー、5000万台の組み込み/モバイルプロセッサー、または上記のすべての組み合わせで実行されているかどうかは気にしません。 Googleがさまざまなチップを使用していることは問題ではありません。自家製の「テンソルプロセッサ」からユニークなシリコンプロセッサ（多くの主要顧客向けにXeonプロセッサ用のチップで販売）、FPGA、GPU、CPU、 D-Wave量子コンピューターなどのさらにエキゾチックな機器まで、 競争力を維持し、中程度の料金でサービスを提供できることが重要です。 結局、今日のスーパーコンピューターは、通常、大量のGPUと異常に高速なInfiniBand接続を備えた多数のラックサーバーのように見えます。 つまり、ご想像のとおり、スーパーコンピューターはデータセンターとそれほど違いはありません。 リストされている機器はどれも、内部のダイナミクスと接続性に応じて、多数の奇妙なマシンをサポートできます。

同様に、任意のAIシステムは、1つの巨大なニューラルネットワークまたは非同期で動作する多くの個別のニューラルネットワークの形で、または異種のマイクロサービスセットとして、または「心の社会」などとして実装できます。 これはすべて特に重要ではありません。 複雑さやリスクの観点から見ると、システムの動作中にシステムがどのように編成されるかはそれほど重要ではありません。 システムは多くのレベルで見ることができ、各レベルはそれ自体では等しく無効ですが、一般的なシステムのさまざまな目的に役立ちます。

ここに、あまり定義されていない質問の例があります。ポケットと机の上に現在何台のコンピューターがありますか？ 「コンピューター」には何台のコンピューターがありますか？ 1つだけだと思いますか？ よく見てみましょう。

CPUだけではありません：現在、トランジスタとプロセッサコアは非常に安価であるため、リアルタイムタスクに別々のコアを割り当て、パフォーマンスを向上させ、セキュリティを確保し、メインOSの負荷を回避し、古いアーキテクチャとの互換性を確保するか、既存のソフトウェアパッケージ。 単に、DSPまたはカーネルは、専用のASICを作成するよりもプログラミングが速いため、または可能な限り最も単純なソリューションであるためです。 さらに、これらのコンポーネントの多くは、意図されていなかったり、この機能を隠している場合でも、計算要素として使用できます。

だから：

• 通常のIntelプロセッサーでは、数十億個のトランジスターが多くのタスクを実行します。
  
  
  • 2-8個のメインプロセッサコアはそれぞれ独立して動作し、必要に応じてオン/オフし、独自のキャッシュ（最近までほとんどのコンピューターのRAMよりも大きい）を備えており、独立したコンピューターと見なす必要があります。
  • CPUは全体として、たとえばマイクロコードを介して再プログラムされ、チップ設計エラーを排除し、Intel Management Engine（ プログラミング用のJVMを使用 ; Rouen、2014およびSGX ）またはAMDのPlatform Security Processor （PSP）などの不透明度を増すオブジェクトを誇示します 。 Android TEE これらのハードウェアモジュールは、原則として、それ自体が本格的なコンピューターであり、ホストとは独立して動作し、その動作を妨げる可能性があります。
  • FRACTRANの精神で、浮動小数点演算でエンコードすることにより、FPUはチューリング完全システムになります。
• 前述のように、 MMUは奇妙なページフォールトマシンにプログラムできます。
• DSPブロック、カスタムチップ。 おそらく、 h.264のようなビデオ形式のASICは、チューリング完全なシステムではありません（Vanタイルのようなものを可能にする複雑なデルタと圧縮方法のサポートにもかかわらず）。 しかし、 Apple A9モバイルSoCは、統合GPUを備えた通常のデュアルコアARMプロセッサーをはるかに超えています。 IntelまたはAMDデスクトップチップと同様に、Secure Enclave（物理的に割り当てられたプロセッサコア）と呼ばれる安全な環境が含まれていますが、画像用のコプロセッサ、音声認識用のコプロセッサ（部分的にSiriをサポートするため）、および明らかに他のいくつかのコアも含まれています。 これらのASICはAIタスク用に存在することがあり、明らかに、ニューラルネットワークの行列乗算に特化しており、リカレントニューラルネットワークはチューリング完全なので、...理解できます。 モトローラ、クアルコム、およびその他の企業も、SoCの拡大に急ぎました。
• マザーボードBIOSおよび/またはネットワークアクセス制御チップ。
  
  
  • マーク・エルモロフは次のように述べています：
    
    

    「インテルSilvermont Moorefield SoC（ANN）に異種プロセッサコアがいくつ統合されているかは驚くべきことです。x86、ARC、LMT、8051、オーディオDSP、それぞれファームウェアとJTAGインターフェイスのサポート

  
  これらの制御またはデバッグチップは、 Via C3 CPUに統合されたARMのように、販売後もデバイスで「誤って」アクティブ化されたままになることがあります 。
• GPUには数百または数千の単純なコアがあり、各コアはニューラルネットワークで非常によく機能するか、汎用の計算を実行します（ただし、プロセッサよりも低速です）。
• テープ、ハードドライブ、フラッシュドライブ、およびSSDコントローラーは通常、ARMプロセッサーで実行され、オペレーティングシステムから不良セクターを隠すなどのタスクのための組み込みユーティリティを実行します。 ハッキングされる可能性があります。 しかし、ARMプロセッサはほとんどの組み込みアプリケーションで使用されているため、ARMは「最新のスマートフォンには8〜14個のARMプロセッサが含まれ、1つはアプリケーションプロセッサ（AndroidまたはiOSを実行）、もう1つは周波数帯域スタック用のプロセッサです」 （ベースバンドスタック） 。 "
• ネットワークチップは、 DMAの独立した処理を実行します（ netbootでの Wake-on-LANなどの独立機能のおかげです）。
• スマートフォン：上記のすべてのブロックに加えて、独自のリアルタイムOSの下で実行され、セルタワー/ GPS /などとの通信を処理する独立したベースバンドプロセッサもあります。 または、L4のような仮想化を使用している場合は複数もあります。 バックドアは、他の脆弱性に加えて、ベースバンドプロセッサで既に検出されています。
• スマートフォン用のSIMカードは、加入者データを記録するメモリカードだけではありません。 これらは、 Java Cardアプリケーション（おそらくNFCチップも）を個別に実行できるスマートカードです。 IMEのJVMのようなものです。 当然、SIMカードはハッキングされ、監視などに使用されます。
• USBまたはマザーボードに接続されたデバイスには、独自のプロセッサを搭載できます。 たとえば、WiFiアダプター、キーボード、マウスなど。理論的には、それらのほとんどはDMAとIOMMUを介したホストとの直接の干渉から隔離されていますが、 悪魔は詳細にあります...
• WatchOSを実行しているMacBook Touchのようなランダムで変なチップ。
• ...

そのため、通常のスマートフォンやデスクトップコンピューターでは、チューリング完全なデバイスという意味で15から数千のコンピューターが存在します。 それらはそれぞれプログラム可能で、多くのプログラムを実行するのに十分な能力を備えており、攻撃者がシステムの残りを監視、抽出、または攻撃するために使用できます。

最初のメインフレームでさえ、通常、メインコンピューターがバッチ処理を実行する複数のコンピューターを含んでおり、補助コンピューターは高速I / O操作を提供するため、これがなければメインマシンに割り込みが干渉します。

実際には、情報セキュリティコミュニティに加えて（これらすべてのコンピューターは安全ではないため、NSAおよびウイルス作成者にとって有用であるため）、他のすべてのユーザーは、コンピューターのフードの下で非常に複雑なシステムであることを気にしません。互いに恥ずかしく接続されたコンピューター（「ネットワークはコンピューター」または「コンピューターはネットワーク」...？）ユーザーはこれを1台のコンピューターとして認識し、使用します。

---

1.研究の活発な分野は、慎重に設計され、チューリング完全でないことを保証される言語とシステムの作成です（たとえば、完全に機能するプログラミング）。なぜ多くのプログラムが書くことができない言語を作成するのにそれほど努力するのですか？事実、チューリングの完全性は、ゲーデルの不完全性定理とライスの定理と密接に関連しています。。したがって、TCが許可された場合、可能性のあるすべての証明可能性が失われます。それどころか、さまざまな有用なことが、チューリングの不完全な言語で簡単に証明されています：たとえば、プログラムが完全であるか、タイプセーフであるか、論理定理に簡単に変換できるか、限られた量のリソースを消費するか、プロトコル実装が真であるか、別の実装と同等であるかなど。副作用がなく、プログラムを論理的に同等であるがより高速なオプションに変換できることを証明するのは簡単です（これは、クエリを変換するオプティマイザーの能力が許容可能なパフォーマンスの鍵であるSQLなどの宣言型言語にとって特に重要です。もちろん、驚くべきことはSQLで行うことができますが、など機械学習モデルの勾配降下、およびいくつかのSQL拡張機能により、とにかくチューリングが完了し、ループシステム、またはmodelDSLをエンコードするか、PL / SQLなどを呼び出すことができます。

変な車に関するいくつかの文献があります：

• 「エクスプロイトプログラミング：バッファオーバーフローから奇妙なマシンや計算理論まで」、Bratus et al。、2011
• 「ネットワークスタックセキュリティの停止問題」 Sassamen et al。、2011
• 「奇妙なページフォールトマシン：指示なしでのコンピューティングの教訓」 Bangert et al。、2013
• 「ELFの奇妙な車：過小評価されたメタデータに焦点を当てる」 Shapiro et al 2013
• 「バグの割り込み指向プログラミング：組み込みシステムのファームウェアにバグを導入するための最小限のアプローチ」、Tan et al。、2014
• 「エビデンスコードの奇妙な車」、Vaneg、2014
• 「サイクリック信号—ポータブルシェルコードに戻る」 Bosman and Bos、2014

↑

2.線形ニューラルネットワークは浮動小数点モードを活用してゼロに丸め、潜在的なチューリング完全な動作をエンコードしますが（RNNの場合）、通常の動作では見えません。これはランダムなチューリング完全な動作であり、安全な言語の良い例です。 ↑

3. ドワーフ要塞は時計仕掛けを提供するため、チューリングの完全性は驚くことではありません。しかし、水は単純なセルオートマトンとしても実装されているため、チューリングの完全性を得るための方法はさらにあります！現在、ゲームwiki では、液体、時計仕掛けのメカニズム、地雷カート、ドアと圧力センサーを備えた生物/動物の論理ゲートなど、論理ゲートを作成する4つの潜在的な方法を挙げています。 ↑

4.完全なPDF仕様は非常に肥大化しています。たとえば、Google Chromeブラウザーなど、十分なPDF仕様をサポートするシンプルなPDFビューアーでは、Breakoutを再生できます（PDFには独自のJavaScriptの奇妙なサブセットが含まれているため）。公式のAdobe PDFビューアは、3次元CADまでの機能をサポートしています。 ↑

5. Think Mathのドミノロジックゲートおよび4ビットドミノナックル加算器のデモを参照してください。 ↑