reductions-展示頁
2025-07-26 16:55本頁面
【正文】 done). ? ∨ ? ∧ ? Negation: ? Power of 2 Player Nash ? It can solve the fixed point problem of a polynomial time putable function. 計(jì)算復(fù)雜性 復(fù)雜性： P vs. NP 問題 ? P：多項(xiàng)式時間可以計(jì)算的問題 ? NP：多項(xiàng)式時間可以驗(yàn)證“正確解”的問題 P：多項(xiàng)式時間可以計(jì)算的問題 ? 匹配：給定二部圖， G＝ (V1,V2。 ? Payoffs ? For Player one: one for s4, s5。s4=(c, 1), (d, 1)。 s2=(b, 1), (d, 1)。 – T停機(jī)與否成為不可判定。 – 結(jié)論： r不可以是有理數(shù)。Reductions 鄧小鐵 上海交通大學(xué) 計(jì)算機(jī)科學(xué)的Reduction （ von Neuman的電腦 ENIAC） 計(jì)算機(jī)科學(xué) 計(jì)算機(jī)應(yīng)用 邏輯電子元件 邏輯電子線路 ? 用 ANDORNOT元件組合的線路 – Universal：可以計(jì)算任何（變量有限）的邏輯函數(shù) ? 應(yīng)用領(lǐng)域 – 自動機(jī) – 計(jì)算機(jī)，空調(diào)，電梯，洗衣機(jī)，電視，手機(jī)， GPS導(dǎo)航，電子游戲，以及許多我們今天已經(jīng)難以離開的現(xiàn)代電子科技產(chǎn)品。 可計(jì)算性理論 可計(jì)算性理論 ? 圖靈機(jī) – 有限態(tài)控制器：狀態(tài)集合，字母集合，轉(zhuǎn)移規(guī)則 – 輸入／輸出紙帶 ? 等價計(jì)算體系 – 遞歸函數(shù) – λ演算 Hilbert（第二）問題 ? 數(shù)學(xué)是完備的嗎？ – 面對那些正確的數(shù)學(xué)陳述，我們是否總能找出一個證明？數(shù)學(xué)真理是否總能被證明？ – Godel: No ? 數(shù)學(xué)是一致的嗎？ – 數(shù)學(xué)是否前后一致，不會得出某個數(shù)學(xué)陳述又對又不對的結(jié)論？數(shù)學(xué)是否沒有內(nèi)部矛盾？ – Godel: No ? 數(shù)學(xué)是可判定的嗎？ – 能夠找到一種方法，僅僅通過機(jī)械化的計(jì)算，就能判定某個數(shù)學(xué)陳述是對是錯？數(shù)學(xué)證明能否機(jī)械化？ – Halting Problem 停機(jī)問題 ? 是否有無理數(shù)？ – 對角化證明：將所有在［ 0， 1］間的有理數(shù)寫成二進(jìn)制數(shù)，排為一序列： r1,r2,…,rn… – 構(gòu)造 r： r的第 i位和 ri的第 i位不同。 ? 能否確定一個圖靈機(jī)會停機(jī)？ – 將圖靈機(jī)排序（按有限態(tài)控制器）： T1,T2,…,Tn,… – 構(gòu)造 T：如果機(jī)器 Ti在輸入 Ti時停機(jī)， T在輸入 Ti時不停機(jī)
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1