比浏览器更快的访问！
19 关系: 功能性問題，停机问题，大卫·希尔伯特，子集，完备性，完備 (複雜度)，布尔可满足性问题，形式系統，形式语言，哥德尔数，算法，相容性，計算複雜性理論，計算資源，递归可枚举集合，递归论，递归集合，L (複雜度)，最佳化問題。
功能性問題
在計算複雜性理論內，功能性問題或者函式問題（function problem）是一種計算問題（:en:computational problem），我們對任何一種輸入都預期會有單一個輸出，但是輸出不像是決定性問題一樣這麼單純。換句話說，輸出不只YES跟NO。重要的範例像是旅行推銷員問題，詢問一張圖是否有可以繞過每一點的不重複路徑（輸出為路徑），以及整數分解，輸出為輸入的質因數。 因為沒有明顯類比的語言，功能性問題比起決定型問題要難以研究。而且因為輸出的可能變多，在解決輸入輸出之間的轉換，功能性問題歸約的過程也比較微妙。功能性問題也可以用像是決定性問題的方式來分成各種複雜度類。舉例來說FP是指可以用確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的P），而FNP是指可以用非確定型圖靈機在多項式時間裡面可以解決的功能性問題（類似於決定性問題的NP）。 對所有能在多項式時間內解決的的功能性問題，一定存在一個雷同的決定型問題，可以用多項式時間圖靈歸約將後者歸約為前者的方式，解決這個功能性問題。舉例，旅行推銷員問題的決定型問題版本如下： 給定這個決定性問題的解答，我們則可以解決旅行推銷員問題如下： 這個演算法將旅行推銷員問題的時間複雜度放進FPNP內（可以在多項式時間之內，以決定性圖靈機和一個能解決NP問題的神諭解決的問題），並且事實上是這個複雜度類的完備問題。.
新！!: 決定性問題和功能性問題 · 查看更多 »
停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。.
新！!: 決定性問題和停机问题 · 查看更多 »
大卫·希尔伯特
大卫·希尔伯特（David Hilbert，），德国数学家，是19世纪和20世纪初最具影响力的数学家之一。希尔伯特1862年出生于哥尼斯堡（今俄罗斯加里宁格勒），1943年在德国哥廷根逝世。他因为发明了大量的思想观念（例：不变量理论、、希尔伯特空间）而被尊为伟大的数学家、科学家。 他提出了希尔伯特空间的理論，是泛函分析的基礎之一。他热忱地支持康托的集合论与无限数。他在数学上的领导地位充分体现于：1900年，在巴黎的国际数学家大会提出的一系列问题（希尔伯特的23个问题）为20世纪的许多数学研究指出方向。 希尔伯特和他的学生为形成量子力学和广义相对论的数学基础做出了重要的贡献。他还是证明论、数理逻辑、区分数学与元数学之差别的奠基人之一。.
新！!: 決定性問題和大卫·希尔伯特 · 查看更多 »
子集
子集，為某個集合中一部分的集合，故亦稱部分集合。 若A和B为集合，且A的所有元素都是B的元素，则有：.
完备性
在数学及其相关领域中，一个对象具有完备性，即它不需要添加任何其他元素，这个对象也可称为完备的或完全的。更精确地，可以从多个不同的角度来描述这个定义，同时可以引入完备化这个概念。但是在不同的领域中，“完备”也有不同的含义，特别是在某些领域中，“完备化”的过程并不称为“完备化”，另有其他的表述，请参考代数闭域、紧化或哥德尔不完备定理。.
完備 (複雜度)
在計算複雜性理論內，一個計算問題(computational problem)對一個複雜度類是完備或者完全的，用比較不正式的解釋，是說這問題在此複雜度類裡面是一個"最難的"或者"最代表性的"題目。如果一個問題的解法可以允許你快速解決這個複雜度類的其他問題的話，我們說這問題對此類別是難(hard)的題目。 更正式的說法是，如果在一個給定的歸約方式之下，所有複雜度類 C裡面的問題都存在某種歸約方式，可以歸約到某個問題p，我們說這個問題p 是C的難問題。如果一個問題是此類別的，且本身是這個類別裡面的一員，則這個問題就是對這個複雜度類完備的(在給定的歸約條件之下)。 一個問題如果對複雜度類C是完備的話，我們會說這個問題是C-完備或者C完全(C-complete)的問題，至於這一些對C是完備問題的集合我們也稱為C-完備。 第一個且是最有名的是NP完全：一個包含許多實際但是不容易的題目。相同的，我們習慣用C難(C-hard)這種用詞稱呼包含所有C難(C-hard)的問題，例如說，NP難。 正常來說我們都假設歸約過程在計算複雜度上面不會比起問題本身要難。因此之故，如果我們對一個C-完備問題有"計算上簡單"的解法的話，則所有在"C"這類別裡面的問題都有"簡單"的解法。 一般說來，有遞歸可枚舉(recursive enumeration)的複雜度類都會有已知的完備問題，而並非如此的類別則沒有已知的完備問題。舉例來說，NP，反NP，PLS，PPA 都有已知的完備問題，而RP，ZPP，BPP和TFNP則沒有已知的完備問題(雖然這不代表未來不會發現完備問題)。 有一些複雜度類是沒有完備問題存在的。舉例來說，Sipser證明了存在一個語言M令BPPM (BPP加上一個M的諭示) 是沒有完備問題的。.
新！!: 決定性問題和完備 (複雜度) · 查看更多 »
布尔可满足性问题
可滿足性（英語：Satisfiability）是用來解決給定的真值方程式，是否存在一组变量赋值，使問題为可满足。布爾可滿足性問題（Boolean satisfiability problem；SAT)）屬於決定性問題，也是第一个被证明屬於NP完全的问题。此問題在電腦科學上許多領域的皆相當重要，包括電腦科學基礎理論、演算法、人工智慧、硬體設計等等。.
新！!: 決定性問題和布尔可满足性问题 · 查看更多 »
形式系統
在邏輯與數學中，一個形式系統（Formal system）是由兩個部分組成的，一個形式语言加上一個推理規則或轉換規則的集合。一個形式系統也許是純粹抽象地制定出來，只是為了研究其自身。另一方面，也可能是為了描述真實現象或客觀現實的領域而設計的。.
新！!: 決定性問題和形式系統 · 查看更多 »
形式语言
在数学、逻辑和计算机科学中，形式语言（Formal language）是用精确的数学或机器可处理的公式定义的语言。 如语言学中语言一样，形式语言一般有两个方面: 语法和语义。专门研究语言的语法的数学和计算机科学分支叫做形式语言理论，它只研究语言的语法而不致力于它的语义。在形式语言理论中，形式语言是一个字母表上的某些有限长字符串的集合。一个形式语言可以包含无限多个字符串。.
新！!: 決定性問題和形式语言 · 查看更多 »
哥德尔数
在形式数论中，哥德尔编号是对某些形式语言的每个符号和公式指派一个叫做哥德尔数(GN)的唯一的自然数的函数。这个概念是哥德尔为证明他的哥德尔不完备定理而引入的。 可计算函数集合的编号有时叫做哥德尔编号或有效编号。哥德尔编号可以被解释为一个编程语言，带有指派哥德尔数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。Roger 等价定理特征化了是哥德尔编号的可计算函数集合的编号。.
新！!: 決定性問題和哥德尔数 · 查看更多 »
算法
-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.
相容性
#重定向 一致性 (邏輯).
計算複雜性理論
计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。 如果一个问题的求解需要相当多的资源（无论用什么算法），则被认为是难解的。计算复杂性理论通过引入数学计算模型来研究这些问题以及定量计算解决问题所需的资源（时间和空间），从而将资源的确定方法正式化了。其他复杂性测度同样被运用，比如通信量（应用于通信复杂性），电路中门的数量（应用于电路复杂性）以及中央处理器的数量（应用于并行计算）。计算复杂性理论的一个作用就是确定一个能或不能被计算机求解的问题的所具有的实际限制。 在理论计算机科学领域，与此相关的概念有算法分析和可计算性理论。两者之间一个关键的区别是前者致力于分析用一个确定的算法来求解一个问题所需的资源量，而后者则是在更广泛意义上研究用所有可能的算法来解决相同问题。更精确地说，它尝试将问题分成能或不能在现有的适当受限的资源条件下解决这两类。相应地，在现有资源条件下的限制正是区分计算复杂性理论和可计算性理论的一个重要指标：后者关心的是何种问题原则上可以用算法解决。.
新！!: 決定性問題和計算複雜性理論 · 查看更多 »
計算資源
在計算複雜度理論內，計算資源（Computational resource）的意思是在特定計算模型之下，解決特定問題所要消耗的資源。 最簡單的計算資源是計算時間，計算解決特定問題需要花費的步驟數；以及記憶體空間，定義解決問題時所要花費的空間。不過，也有很多較為複雜的計算資源定義存在。 討論計算資源是非常有用的，因為我們可以用來研究哪些問題可以在給定的計算資源下得到解答。這樣，我們可以決定哪些演算法是最好的，並且有辦法討論演算法的效率。我們稱呼一個包含所有使用特定數量的資源能解決的題目之集合，為一個複雜度類。有關不同的複雜度類之間的關係，是計算複雜性理論內一個非常重要的研究領域。.
新！!: 決定性問題和計算資源 · 查看更多 »
递归可枚举集合
递归可枚举集合（Recursively enumerable set）是可计算性理论或更狭义的递归论中的一个概念。可数集合S被称为是递归可枚举、计算可枚举的、半可判定的或可证明的，如果.
新！!: 決定性問題和递归可枚举集合 · 查看更多 »
递归论
递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。 数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。.
递归集合
在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具可判定性，如果我们可以构造一个算法，使之能在有限时间内终止并判定一个给定元素是否属于这个集合。更一般的集合的类叫做递归可枚举集合。这些集合包括递归集合，对于这种集合，只需要存在一个算法，当某个元素位于这个集合中时，能够在有限时间内给出正确的判定结果，但是当元素不在这个集合中时，算法可能会永远运行下去（但不会给出错误答案）。.
新！!: 決定性問題和递归集合 · 查看更多 »
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。, Definition 8.12, p. 295.
新！!: 決定性問題和L (複雜度) · 查看更多 »
最佳化問題
最佳化問題（Optimization problem）在數學與電腦科學領域中，是從所有中尋找最優良的解的問題。根據變數是連續的或離散的，最佳化問題可分為兩類：連續最佳化問題與組合優化。 相對於決策問題(Decision problem)、功能性問題(Function problem)，最佳化問題是：從問題的多個解中，求出最佳解。例子：背包問題 Category:數理邏輯.
新！!: 決定性問題和最佳化問題 · 查看更多 »
