形式系統和決定性問題

快捷方式: 差异，相似，杰卡德相似系数，参考。

形式系統和決定性問題之间的区别

形式系統 vs. 決定性問題

在邏輯與數學中，一個形式系統（Formal system）是由兩個部分組成的，一個形式语言加上一個推理規則或轉換規則的集合。一個形式系統也許是純粹抽象地制定出來，只是為了研究其自身。另一方面，也可能是為了描述真實現象或客觀現實的領域而設計的。. 在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.

大卫·希尔伯特

大卫·希尔伯特（David Hilbert，），德国数学家，是19世纪和20世纪初最具影响力的数学家之一。希尔伯特1862年出生于哥尼斯堡（今俄罗斯加里宁格勒），1943年在德国哥廷根逝世。他因为发明了大量的思想观念（例：不变量理论、、希尔伯特空间）而被尊为伟大的数学家、科学家。 他提出了希尔伯特空间的理論，是泛函分析的基礎之一。他热忱地支持康托的集合论与无限数。他在数学上的领导地位充分体现于：1900年，在巴黎的国际数学家大会提出的一系列问题（希尔伯特的23个问题）为20世纪的许多数学研究指出方向。 希尔伯特和他的学生为形成量子力学和广义相对论的数学基础做出了重要的贡献。他还是证明论、数理逻辑、区分数学与元数学之差别的奠基人之一。.

大卫·希尔伯特和形式系統 · 大卫·希尔伯特和決定性問題 · 查看更多 »

形式语言

在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.

形式系統和形式语言 · 形式语言和決定性問題 · 查看更多 »