热门问题
时间线
聊天
视角
可判定性問題
来自维基百科,自由的百科全书
Remove ads
可判定性問題(德語:Entscheidungsproblem,意為「決策問題」)是數學和計算機科學中的一個基本問題,由德國數學家大衛·希爾伯特]和威廉·阿克曼於1928年提出。此問題為是否存在一個通用的方法,能在有限步驟內,判定一個數學命題的真假。[1]
此條目沒有列出任何參考或來源。 (2019年6月10日) |
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
語言的可判定性
一個語言,是一個集合,且其補集為 。
當是圖靈機可識別時,語言則稱為半可判定。
當語言不是圖靈機可識別,則為不可判定語言。
當且僅當和都是圖靈機可識別的時候,L才能稱為可判定語言。
Remove ads
一般意義上的可判定性
指一個詢問真 / 假的問題是否可被回答。若不論一個問題答案為真或為假時均能得出該答案,則稱這個問題、或解決該問題時所用的算法為可判定的;若只能在答案為真時得出、但在答案為假時不能做出判斷,那麼稱為半可判定的;若根本不能得出為真或為假的結論,那麼稱為不可判定的。
參考
參考文獻
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads