ムーアマシン

計算理論において、ムーアマシンとは、現在の出力値が現在の状態のみによって決定される有限状態マシンである。これは、出力値が現在の状態と入力値の両方によって決定されるミーリーマシンとは対照的である。他の有限状態マシンと同様に、ムーアマシンでは、入力は通常、次の状態に影響を与える。したがって、入力は間接的に後続の出力に影響を与える可能性があるが、現在の出力や直近の出力には影響を与えない。ムーアマシンは、1956年の論文「逐次マシンに関する思考実験」でこの概念を発表したエドワード・F・ムーアにちなんで名付けられた。 ^{[ 1 ]}

ムーアマシンは6タプルとして定義できる${\displaystyle (S,s_{0},\Sigma ,\Lambda ,\delta ,G)}$以下の内容から構成される：

• 有限個 の状態${\displaystyle S}$
• 開始状態（初期状態とも呼ばれる）$s0$これは${\displaystyle S}$
• 入力アルファベットと呼ばれる有限集合${\displaystyle \Sigma }$
• 出力アルファベットと呼ばれる有限集合${\displaystyle \Lambda }$
• 遷移関数${\displaystyle \delta :S\times \Sigma \rightarrow S}$状態と入力アルファベットを次の状態にマッピングする
• 出力関数${\displaystyle G:S\rightarrow \Lambda }$各状態を出力アルファベットにマッピングする

この抽象化では、「時間経過に伴う進化」は、状態機械が離散的な「タイマーティック」で時間変化する入力シンボルを参照することによって実現されます。${\displaystyle t_{0},t_{1},t_{2},...}$そして、それらの理想的な瞬間にその内部構成に従って反応するか、あるいはステートマシンが（FIFOのように）次の入力シンボルを待ち、それが到着するたびに反応するようにする。

ムーアマシンは、有限状態トランスデューサの制限されたタイプとみなすことができる。

ムーアマシンとミーリーマシンはどちらも有限状態機械の一種であるため、表現力は同等です。どちらのタイプも正規言語の解析に使用できます。

ムーアマシンとミーリーマシンの違いは、後者では遷移の出力が現在の状態と現在の入力の組み合わせによって決定されることです（${\displaystyle S\times \Sigma }$の領域として${\displaystyle G}$）現在の状態とは対照的に（${\displaystyle S}$の領域として${\displaystyle G}$)状態図として表現すると、

• ムーア型機械では、各ノード（状態）には出力値がラベル付けされます。
• ミーリーマシンでは、各アーク（遷移）には出力値がラベル付けされています。

すべてのムーアマシン${\displaystyle M}$は、同じ状態と遷移、および出力関数を持つミーリー​​マシンと同等である。${\displaystyle G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))}$各状態入力ペアを取得する${\displaystyle (s,\sigma )}$そして収穫量${\displaystyle G_{M}(\delta _{M}(s,\sigma ))}$、 どこ${\displaystyle G_{M}}$は${\displaystyle M}$の出力関数と$\displaystyle \delta _{M}}$は${\displaystyle M}$の遷移関数。

しかし、すべてのミーリーマシンが等価なムーアマシンに変換できるわけではありません。出力が時間的にシフトした、ほぼ等価なムーアマシンにしか変換できないものもあります。これは、状態ラベルと遷移ラベルがペアになって入出力ペアを形成する方法によるものです。遷移を考えてみましょう。${\displaystyle s_{i}\rightarrow s_{j}}$州から${\displaystyle s_{i}}$述べる${\displaystyle s_{j}}$遷移を引き起こす入力${\displaystyle s_{i}\rightarrow s_{j}}$端にラベルを付ける${\displaystyle (s_{i},s_{j})}$その入力に対応する出力は、状態のラベルです。${\displaystyle s_{i}}$[ ^{2 ]これは遷移のソース状態であることに注意してください。したがって、}各入力に対して、出力は入力が受信される前にすでに固定されており、現在の状態のみに依存します。これはE.ムーアによる元の定義です。状態というラベルを使用するのはよくある間違いです。${\displaystyle s_{j}}$遷移の出力として${\displaystyle s_{i}\rightarrow s_{j}}$。

入力/出力の数に応じて分類します。

単純

単純なムーア機械は、入力が1つ、出力が1つです。

• XORを用いたエッジ検出器
• バイナリ加算機
• クロック同期型シーケンシャルシステム（ムーアマシンの一種で、グローバルクロック信号が変化した時のみ状態が変化する）

ほとんどのデジタル電子システムは、クロック付きシーケンシャルシステムとして設計されています。クロック付きシーケンシャルシステムは、グローバルクロック信号が変化したときにのみ状態が変化する、ムーアマシンの制限された形式です。通常、現在の状態はフリップフロップに格納され、グローバルクロック信号はフリップフロップの「クロック」入力に接続されます。クロック付きシーケンシャルシステムは、メタステーブル状態の問題を解決する方法の1つです。典型的な電子ムーアマシンには、現在の状態を出力（ラムダ）にデコードするための組み合わせ論理チェーンが含まれています。現在の状態が変化すると、その変化はチェーン全体に波及し、ほぼ瞬時に出力が更新されます。変化がチェーン全体に波及する短い期間中に出力にグリッチが発生しないようにするための設計手法がありますが、ほとんどのシステムは、その短い遷移時間中のグリッチを無視するか、無関係であるように設計されています。その後、ムーアマシンが再び状態を変化させるまで、出力は無期限に同じ状態を維持します（LEDは明るく点灯したまま、モーターへの電源は接続されたまま、ソレノイドは通電されたままなど）。

実例

シーケンシャルネットワークは、入力が1つ、出力が1つです。入力として0が2つ以上、1が2つ以上出現すると、出力は1になり、その後も1のままです。

上記の説明に対応する9つの状態を持つムーア型マシンを右図に示す。初期状態は状態A、最終状態は状態Iである。この例の状態遷移表は以下のとおりである。

ムーアの1956年の論文「逐次マシンに関する思考実験」 ^{[ 1 ]}では、${\displaystyle (n;m;p)}$オートマタ（または機械）${\displaystyle S}$と定義される${\displaystyle n}$州、${\displaystyle m}$入力シンボルと${\displaystyle p}$出力シンボル。構造に関する9つの定理が証明されています。${\displaystyle S}$、そして実験${\displaystyle S}$。 後で、 "${\displaystyle S}$「機械」は「ムーアの機械」として知られるようになった。

論文の末尾にある「今後の課題」のセクションでは、以下の課題が述べられています。

もう一つ直接的に続く問題は、定理8と定理9で与えられた境界を改善することである。

ムーアの定理8は次のように定式化される。

任意の${\displaystyle (n;m;p)}$機械${\displaystyle S}$、その状態の任意の２つが互いに区別可能であるならば、長さの実験が存在する。${\displaystyle {\tfrac {n(n-1)}{2}}}$状態を決定する${\displaystyle S}$実験の最後に。

1957年、AA カラツバは、ムーアの「定理8」における実験長の限界の改善に関する問題を完全に解決する以下の2つの定理を証明した。

定理A.${\displaystyle S}$は${\displaystyle (n;m;p)}$機械において、その状態の任意の２つが互いに区別可能であるならば、長さが最大で${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$それによって、${\displaystyle S}$実験の最後に。

定理B.存在する${\displaystyle (n;m;p)}$機械の各２つの状態は互いに区別可能であり、実験終了時の機械の状態を確立する最短実験の長さは、${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$。

定理 A と B は、モスクワ国立大学力学・数学学部の学生論文コンテストで 1958 年に推薦状を授与された、4 年生の学生 A.A. カラツバの講義論文「オートマタ理論の一問題について」の基礎として使用されました。カラツバの論文は 1958 年 12 月 17 日に学術誌 Uspekhi Mat. Nauk に提出され、1960年 6 月に同誌に掲載されました。^{[ 3 ]}

現在（2011年）まで、実験の長さに関するカラツバの結果は、オートマトン理論と計算複雑性理論の同様の問題の両方において、唯一の正確な非線形結果である。

• 同期回路
• ミーリーマシン
• アルゴリズム状態機械
• 自律システム（数学）

• コンウェイ、JH（1971）。『正則代数と有限機械』ロンドン：チャップマン・アンド・ホール。ISBN 0-412-10620-5. Zbl 0231.94041 . 
• Moore EF「逐次機械に関する思考実験」『オートマタ研究』『数学研究年報』 34巻、129-153頁。プリンストン大学出版局、プリンストン、ニュージャージー州（1956年）。
• カラツバ AA 有限オートマトン理論の一問題の解法. Usp. Mat. Nauk, 15:3, 157–159 (1960).
• カラツバ AA Experimente mit Automaten (ドイツ語) Elektron。情報動詞。 Kybernetik、11、611–612 (1975)。
• 唐津場AA研究業績一覧

ムーア・アンド・ミーリーマシン

• ウィキメディア・コモンズにあるムーアの機械に関連するメディア