不可判定问题列表 目录 逻辑問題 抽象電腦（Abstract machine）問題 矩陣問題 組合群論（combinatorial group theory）問題 拓扑学問題 可解答性問題 其它問題 參考 导航菜单An Undecidable Property of Definite Integrals

数学列表計算理論递归论計算複雜性理論


[1]




這是一個不可判定问题列表。




目录





  • 1 逻辑問題


  • 2 抽象電腦（Abstract machine）問題


  • 3 矩陣問題


  • 4 組合群論（combinatorial group theory）問題


  • 5 拓扑学問題


  • 6 可解答性問題


  • 7 其它問題


  • 8 參考




逻辑問題



  • 大衛·希爾伯特的可判定性。

  • 二階Λ演算的类型推论和型別檢查。


抽象電腦（Abstract machine）問題



  • 停机问题（決定圖靈機是否停機）

  • 決定圖靈機是否Busy beaver（最長運行的圖靈機有相用的停机问题）


  • 死亡率问题（mortality problem）


  • 萊斯定理指出所有partial方程的非凡屬性，決定機器計算partial方程與其屬性是否未決定。


矩陣問題


  • 矩陣的致命問題：表達，一個有限集合的n × n矩陣的整數項，是否能有規律地倍增，重複出現，生成零矩陣。（已知一組15個或更多的3 × 3的矩陣及2組的45 × 45矩陣是未決定問題）

  • 決定一個有限集合的上三角形3 × 3矩陣與非負整數項能否組成一個自由半群。

  • 決定兩個有限生成的Mn(Z)子半群是否有相同的元素。


組合群論（combinatorial group theory）問題


  • Word problem for groups

  • 共軛問題


  • 群同構問題（Group isomorphism problem）


拓扑学問題


  • 決定兩個有限單形（simplicial complex）是否表現同胚空間。

  • 決定兩個有限單形（simplicial complex）是否（同胚至）流形。

  • 決定有限單的基本群是否密着。


可解答性問題


  • 對於某些類別的方程，問題決定；兩個相用的方程，零的方程，是否不定積分的函數也包括在其中。例如，請參考Stallworth and Roush[1]。(這些問題並非總是不可判定的。這取決於class。例如，Risch algorithm，一个对于属于超越初等函数一个领域，其任何函数的初等积分之有效决定步骤。)

  • “分解問題決定the definite contour multiple integral of an elementary meromorphic function is zero over an everywhere real analytic manifold on which it is analytic。”這被希爾伯特第十問題判定為矛盾而解決。[2]


其它問題



  • 波斯特对应問題（Post correspondence problem）

  • 某些形式語言的word problem

  • 決定王氏砖块是否能铺满平面

  • 判断標記系統是否停机

  • 计算某个字符串的柯氏复杂性


  • 希爾伯特第十問題：決定不定方程（又稱為丟番圖方程）的可解答性。

  • 決定上下文有关语言会否生成对应字母表的所有字符串；或判断其是否有歧义。

  • 兩個上下文有关语言能否生成同樣的字符串，或一個语言生成另一個语言生成的子集，或是否有某个字符串两个语言都生成。

  • 給予一個為初始點的有理坐標是週期性，決定位於basin of attraction是否開集，或是否在平分線函數迭代為兩個綱比或三個綱比。

  • 決定Λ演算方程是否有正則形式。


參考



  1. ^ Stallworth, Daniel T. and Fred W. RoushAn Undecidable Property of Definite Integrals Proceedings of the American Mathematical Society Volume 125, Number 7, July 1997, Pages 2147-2148


  2. ^ S&R

Brookshear, J. Glenn. Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 1989.  Appendix C includes impossibility of algorithms deciding if a grammar contains ambiguities, and impossibility of verifying program correctness by an algorithm as example of Halting Problem.


Halava, Vesa. Decidable and undecidable problems in matrix theory. TUCS technical report 127. Turku Centre for Computer Science. 1997. 
[1]


B. M. E. Moret, H. D. Shapiro. Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 1991.  Discusses intractability of problems with algorithms having exponential performance in Chapter 2, "Mathematical techniques for the analysis of algorithms."


Weinberger, Shmuel. Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. 2005.  Discusses undecidability of the word problem for groups, and of various problems in topology.







-

Popular posts from this blog

名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠－名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局编编

Image
東螺溪清水溪加走寮溪阿里山溪東埔蚋溪獅尾堀清水溪清水溝溪水里溪陳有蘭溪郡坑溪十八重溪那馬嘎班溪松柏坑溪卓棍溪瓠瓢坑溪益則坑溪玉崙溪丹大溪郡大溪巒大溪卡社溪栗栖溪萬大溪萬大北溪萬大南溪霧社溪塔羅灣溪馬赫坡溪萬大發電廠大觀發電廠日月潭第一發電所明潭發電廠鉅工分廠水里機組濁水機組名間水力發電廠西濱大橋自強大橋高鐵濁水溪橋西螺大橋溪州大橋中沙大橋彰雲大橋台鐵濁水溪橋國道三號濁水溪橋名竹大橋集集橋集鹿大橋玉峰大橋永興橋龍神橋靜和橋寶石橋雙龍橋雙龍吊橋孫海橋思源橋松林橋親愛橋濁水溪橋德魯灣橋雲龍橋 名間鄉臺灣水力發電廠 臺灣水力發電廠南投縣名間鄉集集攔河堰集集攔河堰濁水溪台灣BOT水力發電廠經濟部經濟部水利署集集攔河堰名間鄉名間水力公司日本關西電力公頃台灣電力公司 body.skin-minerva .mw-parser-output table.infobox captiontext-align:center 名間水力發電廠 名間水力發電廠 名間水力發電廠在臺灣的位置 國家   中華民國 位置 南投縣名間鄉濁水村 坐標 23°50′10″N 120°42′41″E  /  23.83611°N 120.71139°E  / 23.83611; 120.71139 坐标： 23°50′10″N 120°42′41″E  /  23.83611°N 120.71139°E  / 23.83611; 120.71139 現況 運轉中 始建日期 2004年 啟用日期 2007年 建造費用 新台幣832,858,000元 持有單位 經濟部水利署 运营单位 名間水力公司 建造者 名間水力公司 設計監造：中興工程顧問公司 機電工程：大將作公司 土建工程：順達營造工程公司 慣常式水力發電 水力發電形式 川流式水力發電 取水來源 濁水溪 發電機型號 額定容量9280kV，同步發電機兩部 水輪機型號 豎軸卡布蘭式水輪機兩部 廠房類型 半地下式 壓力鋼管 兩條，長113公尺、直徑4公尺 水頭高度 有效落差31.0公尺 用水量 單部：16.704CMS 兩部：33CMS 發電概況 额定容量 16.704MW 年发电量 每年約7,594萬度 名間水力發電廠 ，是臺灣一座小型水力發電廠，位於南投縣名間鄉濁水村集集攔河堰下游五公里，於2007年啟用，係利用集集攔河堰截取濁水溪之水源發電
Read more

Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

Image
Is a conference paper whose proceedings will be published in IEEE Xplore counted as a publication? Prove that NP is closed under karp reduction? Is it important to consider tone, melody, and musical form while writing a song? How is it possible to have an ability score that is less than 3? Can I make popcorn with any corn? Mathematical cryptic clues tikz: show 0 at the axis origin Minkowski space can i play a electric guitar through a bass amp? Why not use SQL instead of GraphQL? How can I prevent hyper evolved versions of regular creatures from wiping out their cousins? How old can references or sources in a thesis be? Do VLANs within a subnet need to have their own subnet for router on a stick? How to add double frame in tcolorbox? How much RAM could one put in a typical 80386 setup? "You are your self first supporter", a more proper way to say it How is the claim "I am in New York only if I am in America" the same as "If I am
Read more

Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar

Image
Is the Mordenkainen's Sword spell underpowered? Escaping $ in listings environment Short story about astronauts fertilizing soil with their own bodies No invitation for tourist visa but I want to visit Do regular languages belong to Space(1)? Can I take recommendation from someone I met at a conference? How to name indistinguishable henchmen in a screenplay? Found this skink in my tomato plant bucket. Is he trapped? Or could he leave if he wanted? How can I prevent/balance waiting and turtling as a response to cooldown mechanics Can I feed enough spin up electron to a black hole to affect it's angular momentum? Why does BitLocker not use RSA? Is my guitar’s action too high? Does GDPR cover the collection of data by websites that crawl the web and resell user data Trying to enter the Fox's den How to achieve cat-like agility? "Destructive power" carried by a B-52? Should man-made satellites feature an intelligent inverted "cow c
Read more