Turing Machine Simulator RHON and a Method for Its Minimization

有限個の連続値出力ニューロンからなる再帰型ニューラルネットワークは，任意の決定性チューリング機械を実時間でシミュレート[3]，[16]できる．これまで提案されたシミュレートモデルでは，有限状態制御部の状態をニューロン出力で局所的に表現しているため，シミュレートするチューリング機会に応じてネットワーク構成と結合重みを変更する必要がある．本論文では，制御部の状態をテープと同様にニューロンの連続値出力として符号化することで，定数個のニューロンによりチューリング機械シミュレータが構成できることを示す．まず，しきい値関数，線形関数，方形関数を入出力関数に用いる有限個のニューロンからなる再帰型高次結合ニューラルネットワークが，任意の決定性チューリング機械を実時間でシミュレートでき，シミュレートに要するニューロン数を有限状態制御部の状態数+4まで削減できることを示す．この結果をもとに，読み出すテープ記号に応じた，状態遷移，シフト操作，書換え操作を入出力関数で実現することで，11個のニューロンによりシミュレータを構成できることを示す．テープと有限状態制御部をニューロン出力として畳み込む方法は，連続値の演算に基づく新たな計算モデルを構成する上で有用な枠組みとなる