ハートマニス・スターンズ予想

コンピュータサイエンスにおける未解決問題

実際の拡大${\displaystyle x}$ある基地で${\displaystyle b\geq 2}$リアルタイムで計算可能で、${\displaystyle x}$合理的か、それとも超越的か？

コンピュータサイエンスにおける未解決問題

理論計算機科学と数学において、ハートマニス・スターンズ予想は、1965年の論文でこの予想を提起し、計算複雑性理論の分野を創設したジュリス・ハートマニスとリチャード・E・スターンズにちなんで名付けられた未解決問題である^{[ 1 ]}（彼らは1993年にACMチューリング賞を受賞した）。

無限語は、入力なしで実行され、連続する文字間の時間差が一定であるマルチテープチューリングマシンが存在し、その単語の連続する文字を出力テープに書き込む場合、リアルタイムで計算可能であると言われる。言い換えれば、自然数が与えられたとき、${\displaystyle n}$単項出力では最初の${\displaystyle n}$時間の中の単語の文字${\displaystyle O(n)}$[ ^{2 ] [ 3 ]}ハートマニス・スターンズ予想は、^もし${\displaystyle x}$ある基数で展開すると、実数となる。${\displaystyle b\geq 2}$（例：${\displaystyle b=10}$）はリアルタイムで計算可能であり、${\displaystyle x}$合理的または超越的である。^{[ 4 ] [ 3 ]}

この予想は、整数乗算アルゴリズムが存在しないことを深く示唆している。${\displaystyle O(n)}$（一方、${\displaystyle O(n\log(n))}$アルゴリズムは既知である）。^{[ 3 ]}

部分的な結果はボリス・アダムチェフスキとヤン・ビュジョーによって証明された^{[ 5 ]} （ジョン・H・ロクストンとアルフレッド・ファン・デル・ポーテンによる以前の証明^{[ 6 ]}には欠陥があることが判明した）。${\displaystyle x}$拡張が合理的または超越的である場合${\displaystyle x}$ある基地で${\displaystyle b\geq 2}$これは自動シーケンスです。これは後にボリス・アダムチェフスキ、ジュリアン・カセーニュ、マリオン・ル・ゴニデック^{[ 4 ]}によって決定論的プッシュダウンオートマトンによって生成されるシーケンスに一般化されました。