5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

山口人生〜ストリートダンスの連中に絡まれるの巻 Part21

1 :132人目の素数さん:2005/05/11(水) 04:36:03
参拝先:大神帝山口大先生超教授のサイトIII
http://www.int2.info/news1.htm

前スレ:山口人生 〜超無職、失意の実家帰り〜 Part20
http://science3.2ch.net/test/read.cgi/math/1113806284/

過去スレ、関連スレは>>2-5あたりで。

525 :山口氏の誤読(1):2005/05/18(水) 08:51:40
山口人生(または取り巻きの天使)がどのようにCook還元の論文 を誤読
したか、私の推理を述べる。
はじめは、山口人生がどのように誤解していたかまったくわからなかっ
たが、一連の書き込みを見て気づいたことがある。

その前に、用語を統一するため、Cook還元を軽くさらおう。

(1)巨大な正方形のタブローを用意する。タブローの各セルは、チューリング
テープの文字かチューリング機械の有限常態かどちらかを書けるようになっ
ている。
(2)タブローの最上位行は、チューリング機械の初期状態が記入される。
(3)タブローの2行目以下は空欄になっている。

ここで、Cook はタブローの空欄に次の規則ではめ込みパズルを行うことを
考えた。

(4)タブローの各セルにチューリングテープの文字かヘッドの位置に有限状態
を記入し、かつn+1行目がn行目の(チューリング機械の)次ステップ
になるように設定する。
(5)はめ込みパズルがaccept状態まで到達するかどうか見る。

このとき、(5)でaccept に到達することは、チューリング機械が受理計算を
持つことを意味する。
このはめ込みパズルを論理式に変換するための方法が、Cookの論文で最も
難解な部分であるが、目的は明白である。

世間の一般的な理解(Cook本人と同様の理解)は、(3)の2行目以降が空欄の
タブローを論理式に変換する。


526 :山口氏の誤読(2):2005/05/18(水) 08:52:05
--------------------世間の理解する対応関係-----------------------
最上位行を除いて空欄のタブロー <-> SATの論理式
受理計算の過程 <-> 論理式を充足させる代入
つまり、上記(3)の段階で論理式に対応させる。受理計算を持つかどうか
が、充足する代入を持つかどうかに対応する。
-----------------------------------------------------------------

ところが山口氏は次のように誤読している。
--------------------山口氏の理解する対応関係---------------------
受理計算を書き込んだタブロー <-> SATの論理式
受理計算をもつ場合に限って、論理式が構成できる。つまり上記(5)の
受理計算を見てから論理式を作ると誤解したのだ。
-----------------------------------------------------------------

これでは、受理計算を持たない(不正解入力)のTMから対応する論理式が
作れないのは当然だ。
山口氏は、「不正解入力の行き先指定不要」を対応する論理式が不要と解釈
したのだ。これでは山口氏がうろたえるのも無理は無い。
査読者は、山口氏がここまで愚かと思わないので、「行き先指定不要」と
言ったのだ。
「行き先指定不要」は山口氏が言うように、論理式が存在しないのではない。

正解入力だろうと、不正解入力だろうと論理式は存在する。(山口氏の誤解)

受理計算が見つからない場合は、対応する論理式の具体的な代入が見つから
ないだけである。


527 :山口氏の誤読(3):2005/05/18(水) 08:52:29
山口氏(または天使)がこのように誤読した状況証拠を列挙しよう。

(a) 不正解入力なら α∧¬α で Cookの負け

これは非常に難解だったが、つまり不正解入力で対応する論理式が見つから
ないなら上記 α∧¬α (自明な充足不能論理式)に対応させてしまえば、
否定計算が決定性多項式時間になるから矛盾・・・といいたかったのだろう。

(b) つまり、「p(n)でaccept」を表現した節を除けばどうなるかだ?
(c) つまり、本質的に、「p(n)でaccept」の1・0代入だけが、
wの正解・不正解のキーになるかどうかだ。
それならば、残りの節は、ダミーじゃないか。

これも同様の誤読に起因する。受理計算が終了して、すでにaccept状態の セルが
タブロー上にあるのを確認してから論理式を構成すると思っている。
これでは、論理式を見るまでもなく充足するのは明らか。 このように誤読したまま
では、Cookが馬鹿に見えても仕方がないが・・・オカシイのが誰かはもう明らか。
昔から明らかだったが、山口氏は単にCook還元を理解できていないという、
唯それだけのことだ。

天使たちよ。Cookを馬鹿にするのは、Cookの論文を正しく理解してからにしろ。


290 KB
★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)