n-dim FRACTRANプログラミング言語と一般化3x+1問題への応用

藤井, 大輔

一般のプログラミング言語が文字列をソースコードとして定義されるのに対して，J.H. Conwayの定義したFRACTRANは「分数の列」からなる一風変わったプログラミング言語である．ConwayはFRACTRAN言語のチューリング完全性を通じて，一般化3x+1問題（コラッツ予想）が決定不能問題であることを証明した．発表者は，FRACTRAN言語を多変数に拡張したn-dim FRACTRAN言語を定義し，その基本的性質を通じて一般化3x+1問題に関する既知の定理に対し，行列のスペクトル分解を用いた別証明を与えた．本発表では，FRACTRANの生まれた歴史的背景から，n-dim FRACTRANの定義とその基本的性質（coprimeの補題），上記の別証明などについて紹介する．また，さまざまな（n-dim）FRACTRAN言語のサンプルコードとその挙動を観察・鑑賞することは面白い．時間の許す限り多くのプログラム動作例を紹介したい．発表者は本研究会において，n-dim FRACTRAN言語の教育題材的価値を含めた広義の応用可能性について議論ができればと希望している．

While ordinary programming languages treat strings as its source code, programming language FRACTRAN defined by J.H. Conway is an “esoteric” programming language consisting of “tuple of fractions”. Conway proved that generalized Collatz conjecture is an undecidable problem using Turing completeness of the FRACTRAN language. Presenters defined the n-dim FRACTRAN language which extended the FRACTRAN language to multivariable, and gave different proof with spectral decomposition to the known theorem on generalized Collatz conjecture through n-dim FRACTRAN language and its basic property. In this presentation, we introduce the historical background why FRACTRAN was born, and show the definition of n-dim FRACTRAN and its basic properties (lemma of coprime), and the alternative proof we mentioned before. Also, it is interesting to observe behaviors of the various sample codes of (n-dim) FRACTRAN language. I would like to introduce many examples of program as far as time permits. The presenter hopes that we can discuss the applicability of the n-dim FRACTRAN language in a broad sense including the educational material value through this study group.

n-dim FRACTRANプログラミング言語と一般化3x+1問題への応用

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報詳細情報について

書き出し

問題の指摘

n-dim FRACTRANプログラミング言語と一般化3x+1問題への応用

書誌事項

この論文をさがす

抄録

収録刊行物

キーワード

詳細情報 詳細情報について

書き出し

問題の指摘

参加プロジェクトリスト

詳細情報詳細情報について