[過去ﾛｸﾞ] 巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
938(3): 2017/11/10(金)22:22 ID:pCZUaY/a(1) AAS
チューリング完全の正確な定義ってしらんけど
>Σ(n)-n^2個の無駄な状態を経ないと正しい値を出してくれない恣意的な計算モデル
これはチューリング完全の定義に反しないの？
シミュレートする際の状態数は定数倍じゃなきゃいけないとかなんかないのか？
944: 2017/11/15(水)22:35 ID:ZlhZzSu7(1) AAS
>>934とか>>938とかです
946: 2017/11/16(木)20:11 ID:oLrfjJ5r(1) AAS
Turing完全な計算モデルとはTuring機械で計算可能な任意の問題をその計算モデルで計算できれば良いのであって
計算量のオーダーがTuring機械のそれと一致する（高々、定数倍の違いしかない）ことを保証する必要はない
従って>>934が正しく>>932や>>938は間違い
949: 2017/11/17(金)18:15 ID:erPTciY2(1/2) AAS
>>934や>>938の言ってることがよくわからない
>・・・正しい値を出してくれない恣意的な計算モデル
の正しい値って、ビジービーバー関数の値？
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.027s