比浏览器更快的访问！
28 关系: 停机问题，可计算性理论，实数，寄存器机，库尔特·哥德尔，哥德尔、埃舍尔、巴赫，图灵完全，图灵机，算法，精神哲学，组合子逻辑，羅傑·潘洛斯，马尔可夫算法，超计算，輾轉相除法，阿隆佐·邱奇，量子力学，自然数，艾伦·图灵，雅克·埃尔布朗，通用圖靈機，递归，递归函数，決定性問題，波斯特-图灵机，最大公因數，斯蒂芬·科尔·克莱尼，施普林格科学+商业媒体。
停机问题
停机问题（）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了，不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义，这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述，则其本质问题为: 给定一个图灵机T，和一个任意语言集合S，是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的，可数的（countable）S 也是可停机的。 停机问题包含了自我指涉，本质是一阶逻辑的不自洽性和不完备性，类似的命题有理发师悖论、全能悖论等。.
新！!: 邱奇－图灵论题和停机问题 · 查看更多 »
可计算性理论
在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。.
新！!: 邱奇－图灵论题和可计算性理论 · 查看更多 »
实数
实数，是有理數和無理數的总称，前者如0、-4、81/7；后者如\sqrt、\pi等。实数可以直观地看作小數（有限或無限的），它們能把数轴「填滿」。但僅僅以枚舉的方式不能描述實數的全體。实数和虚数共同构成复数。 根据日常经验，有理數集在數軸上似乎是「稠密」的，于是古人一直认为用有理數即能滿足測量上的實際需要。以邊長為1公分的正方形為例，其對角線有多長？在規定的精度下（比如誤差小於0.001公分），總可以用有理數來表示足夠精確的測量結果（比如1.414公分）。但是，古希臘畢達哥拉斯學派的數學家發現，只使用有理數無法完全精確地表示這條對角線的長度，這徹底地打擊了他們的數學理念；他們原以為：.
新！!: 邱奇－图灵论题和实数 · 查看更多 »
寄存器机
在数理逻辑和理论计算机科学中，寄存器机（Register machine），又譯為暫存器機，是以类似于使用图灵机的方式使用的一类抽象機器。所有模型都是图灵等价的。 寄存器机得名于它有一个或多个“寄存器”——替代了图灵机的磁带和磁头，这个模型使用了多个唯一寻址的寄存器，每个都持有一个单一正整数。 在文献中至少可找到4个子类，下面按最原始到最类似计算机的次序列出：.
新！!: 邱奇－图灵论题和寄存器机 · 查看更多 »
库尔特·哥德尔
库尔特·弗雷德里希·哥德尔（Kurt Friedrich Gödel，），出生於奧匈帝國的數學家、邏輯學家和哲學家，维也纳学派（维也纳小组）的成员。其最杰出的贡献是哥德尔不完备定理和连续统假设的相对协调性证明。.
新！!: 邱奇－图灵论题和库尔特·哥德尔 · 查看更多 »
哥德尔、埃舍尔、巴赫
《哥德尔、埃舍尔、巴赫：集異璧之大成》（Gödel, Escher, Bach: an Eternal Golden Braid），是一本贏得普立茲獎的書。它是侯世達的著作，由Basic Books出版社在1979年出版的。這本書的二十周年版本在1999年發行，而且由侯世達加上新的前言。《集異璧之大成》（ISBN 7-100-01323-2）是商务印书馆在1996年出版的根据1995年英文版翻译的中文版。本书的英文副标题意译为“一条永恒的金带”，其首字母与哥德尔、埃舍尔、巴赫三人的英文名字首字母GEB相同，而商务印书馆中文译本的副标题中的“集異璧”则与GEB谐音。 本书一共有两篇，上篇译为“集异璧 GEB”，下篇译为“异集璧 EGB”。 本書主要講述了邏輯學家哥德尔，藝術家埃舍尔，和作曲家巴赫的创造性的成就怎樣交織在一起。正如作者所說：“我認識到，哥德尔、埃舍尔和巴赫只是用不同的方式來表達一样相同的本質。我嘗試重現這种本質而寫出這本書。” 此書在深层次上并非研究這三個人。那只不過是通往該書中心主題的其中一條路——侯世達在序言指出：“到底文字和思想是否依從俱形式的規則？這正是此書的中心問題。”（Do words and thoughts follow formal rules, or do they not? That problem is the problem of this book.）.
新！!: 邱奇－图灵论题和哥德尔、埃舍尔、巴赫 · 查看更多 »
图灵完全
#重定向 圖靈完備性.
新！!: 邱奇－图灵论题和图灵完全 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: 邱奇－图灵论题和图灵机 · 查看更多 »
算法
-- 算法（algorithm），在數學（算學）和電腦科學之中，為任何良定义的具體計算步驟的一个序列，常用於計算、和自動推理。精確而言，算法是一個表示爲有限長列表的。算法應包含清晰定義的指令用於計算函數。 算法中的指令描述的是一個計算，當其時能從一個初始狀態和初始輸入（可能爲空）開始，經過一系列有限而清晰定義的狀態最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化算法在内的一些算法，包含了一些隨機輸入。 形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，並在其后尝试定义或者中成形。这些尝试包括库尔特·哥德尔、雅克·埃尔布朗和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義爲形式化算法的情況。.
新！!: 邱奇－图灵论题和算法 · 查看更多 »
精神哲学
心靈哲學（英語：philosophy of mind）或精神哲学是一个研究心靈、心理事件、心理功能、心理特性、意識以及它们與肉體（尤其是大腦）的關係的本质的哲學分支。雖然有很多有關心靈的課題都與肉體無關，但是大眾總認為「心靈與肉體的關係」是核心的研究對象。 Kim, J., "精神哲学的问题".
新！!: 邱奇－图灵论题和精神哲学 · 查看更多 »
组合子逻辑
组合子逻辑是Moses Schönfinkel和哈斯凱爾·加里介入的一种符号系统，用来消除数理逻辑中对变量的需要。它最近在计算机科学中被用做计算的理论模型和设计函数式编程语言的基础。它所基于的组合子是只使用函数应用或早先定义的组合子来定义从它们的参数得出的结果的高阶函数。.
新！!: 邱奇－图灵论题和组合子逻辑 · 查看更多 »
羅傑·潘洛斯
羅傑·潘洛斯爵士，OM，FRS（Sir Roger Penrose，），英國數學物理學家與牛津大學數學系W. W. Rouse Ball名譽教授。他在數學物理方面的工作擁有高度評價，特別是對廣義相對論與宇宙學方面的貢獻。他也是娛樂數學家與具爭議性的哲學家。羅傑·潘洛斯是科學家理昂內·潘洛斯與的兒子，為數學家與西洋棋大師強納森·潘洛斯的兄弟。.
新！!: 邱奇－图灵论题和羅傑·潘洛斯 · 查看更多 »
马尔可夫算法
尔可夫算法是使用类似形式文法的规则在符号串上操作的字符串重写系统。马尔可夫算法被证明是图灵完全的，这意味着它们适合作为一般的计算模型，并可以用它的简单概念表示任何数学表达式。 Refal是基于马尔可夫算法的编程语言。.
新！!: 邱奇－图灵论题和马尔可夫算法 · 查看更多 »
超计算
超计算或超图灵计算可以输出非图灵可计算结果的计算模型。例如，一台可以解决停机问题的机器可算作一台超计算机；可以正确推演皮亚诺算术中每一个状态的机器亦然。 邱奇－图灵论题指出，任何可以用有限算法以纸笔计算的"可有效计算"函数都能被图灵机计算。超计算机能计算图灵机无法计算、即邱奇－图灵论题中不可计算的的函数。 严格说来概率图灵机的输出是不可计算的。然而，大多数超计算方向的文献更关注有用的计算而非随机、不可计算的函数。.
新！!: 邱奇－图灵论题和超计算 · 查看更多 »
輾轉相除法
在数学中，辗转相除法，又称欧几里得算法（Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。 两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（）；因为，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如。这个重要的結論叫做貝祖定理。 辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中歷史最悠久的。这个算法原先只用来处理自然数和几何长度（相當於正實數），但在19世纪，辗转相除法被推广至其他类型的數學對象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。 辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同時這也標誌著计算复杂性理论的開端。.
新！!: 邱奇－图灵论题和輾轉相除法 · 查看更多 »
阿隆佐·邱奇
阿隆佐·邱奇（Alonzo Church，）是美国数学家，1936年发表可计算函数的第一份精确定义，对算法理论的系统发展做出巨大贡献。邱奇在普林斯顿大学受教并工作四十年，曾任数学与哲学教授。1967年迁往加利福尼亚大学洛杉矶分校。 解决算法问题包括构造一个能解决某一指定集及其他相关集的算法，如果该算法无法构建，则表明该问题是不可解的。证明此种问题不可解性的定理是算法理论中的一大突破，邱奇的算法即为该类算法的首例。邱奇证明了基本几何问题的算法不可解性。同时证明了一阶逻辑中真命题全集的解法问题是不可解的。.
新！!: 邱奇－图灵论题和阿隆佐·邱奇 · 查看更多 »
量子力学
量子力学（quantum mechanics）是物理學的分支，主要描写微观的事物，与相对论一起被认为是现代物理学的两大基本支柱，许多物理学理论和科学，如原子物理学、固体物理学、核物理学和粒子物理学以及其它相关的學科，都是以其为基础。 19世紀末，人們發現舊有的經典理論無法解釋微观系统，於是經由物理學家的努力，在20世紀初創立量子力学，解釋了這些現象。量子力學從根本上改變人類對物質結構及其相互作用的理解。除透过广义相对论描写的引力外，迄今所有基本相互作用均可以在量子力学的框架内描述（量子场论）。 愛因斯坦可能是在科學文獻中最先給出術語「量子力學」的物理學者。.
新！!: 邱奇－图灵论题和量子力学 · 查看更多 »
自然数
数学中，自然数指用于计数（如「桌子上有三个苹果」）和定序（如「国内第三大城市」）的数字。用于计数时称之为基数，用于定序时称之为序数。 自然数的定义不一，可以指正整数 (1, 2, 3, 4, \ldots)，亦可以指非负整数 (0, 1, 2, 3, 4, \ldots)。前者多在数论中使用，后者多在集合论和计算机科学中使用，也是 标准中所采用的定义。 数学家一般以\mathbb代表以自然数组成的集合。自然数集是一個可數的，無上界的無窮集合。.
新！!: 邱奇－图灵论题和自然数 · 查看更多 »
艾伦·图灵
艾伦·麦席森·图灵，OBE，FRS（Alan Mathison Turing，又译阿兰·图灵，Turing也常翻譯成--林或者杜林，）是英国計算機科學家、数学家、邏輯學家、密码分析学家和理论生物学家，他被视为计算机科学與人工智慧之父。 在第二次世界大战期间，图灵曾在“政府密码学校”（GC&CS，今政府通信总部）工作。政府密码学校位于布萊切利園，是英国顶级机密情报机构。图灵在这里从事密码破译工作，有一段时间，他领导了（Hut 8）小组，负责德国海军密码分析。 期间他设计了一些加速破译德国密码的技术，包括改进波兰战前研制的机器，一种可以找到恩尼格玛密码机设置的机电机器。 图灵在破译截获的编码信息方面发挥了关键作用，使盟军能够在包括大西洋战役在内的许多重要交战中击败纳粹，并因此帮助赢得了战争。 图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《》的论文，提問「机器会思考吗？」（Can Machines Think?），作為一种用于判定机器是否具有智能的测试方法，即图灵测试。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。 图灵是著名的男同性恋者，并因为其性倾向而遭到当时的英国政府迫害，职业生涯尽毁。他亦患有花粉过敏症。 图灵还是一位世界级的长跑运动员。他的马拉松最好成绩是2小時46分03秒（手動計時），比1948年奥林匹克运动会金牌成绩慢11分钟。1948年的一次跨国赛跑比赛中，他跑赢了同年奥运会银牌得主。.
新！!: 邱奇－图灵论题和艾伦·图灵 · 查看更多 »
雅克·埃尔布朗
雅克·埃尔布朗（Jacques Herbrand，），法国数学家。生于巴黎。毕业于巴黎高等师范学校学习，21岁获博士学位，后出国到德国游学。游学期间与冯·诺伊曼、阿廷、诺特等人相识。1931年夏在阿尔卑斯山爬山时，不幸遇险身亡，年仅23岁。 埃尔布朗的主要贡献在数理逻辑和类域论，发明了递归函数。他建立的埃尔布朗定理是量化理论的一个基本命题，已成为机器证明的基础。在近世代数方面，他发表了十几篇有关类域论的论文，丰富了代数数域的阿贝尔扩张理论。.
新！!: 邱奇－图灵论题和雅克·埃尔布朗 · 查看更多 »
通用圖靈機
通用图灵机（Universal Computing Machine，又称Machine U）是一种图灵机，由艾伦·图灵在1936年发明。这种多用途單機器（計算機器）模型可以「運行」任何任意（但well-formed）指令序列（稱為 "quintuples"）。這模型被一些人例如Davis (2000) 認為是「存儲程序電腦」的原點。存儲程序電腦一詞由约翰·冯·诺伊曼使用在他的《電子計算裝置》（"Electronic Computing Instrument"）。這種電腦現在使用冯·诺伊曼的名字稱為冯·诺伊曼结构。 這機器作為計算模型現在稱為「通用圖靈機」。.
新！!: 邱奇－图灵论题和通用圖靈機 · 查看更多 »
递归
递归（Recursion），又译为--，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。.
新！!: 邱奇－图灵论题和递归 · 查看更多 »
递归函数
在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。 其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 所有递归函数的集合叫做R。.
新！!: 邱奇－图灵论题和递归函数 · 查看更多 »
決定性問題
在可計算性理論與計算複雜性理論中，所謂的決定性問題（Decision problem）是一個在某些形式系統回答是或否的問題。例如：「給兩個數字x與y，x是否可以整除y？」便是決定性問題，此問題可回答是或否，且依據其x與y的值。 決定性問題與功能性問題（Function problem，或複雜型問題）密切相關，功能性問題的答案內容，較簡單的是與非複雜許多。範例問題：「給予一個正整數x，則哪些數可整除x？」 另一個與上述兩類問題相關的是最佳化問題（Optimization problem），此問題關心的是尋找特定問題的最佳答案。 解決決定性問題的方法稱為決策程式或演算法。一個針對決定性問題的演算法將說明給予參數x和y的情況下如何決定x是否整除y。若是某些決定性問題可以被一些演算法所解決，則稱此問題可決定。 計算複雜度的領域中，分類可決定問題的依據在於此問題有多難被解決。在此標準下，所謂的難是以解決某問題最有效率的演算法所花費的計算資源為依據。在遞迴理論中，非決定性問題由圖靈度決定，指的是一種在任何解答中隱含的不可計算性量詞。 計算性理論的研究集中在決定性問題上。在與功能性問題的等值問題中，並沒有失去其普遍性。.
新！!: 邱奇－图灵论题和決定性問題 · 查看更多 »
波斯特-图灵机
Post-图灵机是一种特别简单类型的图灵机的"程序公式化"，由下面描述的Emil Post的图灵等价的计算模型构成。（Post的模型和图灵的模型，尽管相互之间非常类似，但却是独立开发的。图灵的论文在1936年五月出版，Post的论文在十月出版。）Post-图灵机使用二元字母表，无限序列的二元存储位置，和带有在存储位置上双向移动和一次一个更改其内容的指令的原始编程语言。"Post-图灵程序"和"Post-图灵机"的名字由Martin Davis在1973年-1974年使用（Davis 1973, p.69ff）。后来Davis在1980年使用名字"Turing-Post程序"（Davis, in Steen p. 241）。.
新！!: 邱奇－图灵论题和波斯特-图灵机 · 查看更多 »
最大公因數
数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：.
新！!: 邱奇－图灵论题和最大公因數 · 查看更多 »
斯蒂芬·科尔·克莱尼
斯蒂芬·科尔·克莱尼（Stephen Cole Kleene，）美國數學家、逻辑學家，主要从事對可計算函數的研究，而他的遞歸理論研究有助於奠定理論電腦科學的基礎。他為數學直覺主義的基礎做出了重要貢獻，克莱尼層次結構、克莱尼代数、克莱尼星号（克莱尼閉包）、克莱尼遞歸定理和克莱尼不動點定理數學概念以他的名字命名。他也是正規表示法的發明者。.
新！!: 邱奇－图灵论题和斯蒂芬·科尔·克莱尼 · 查看更多 »
施普林格科学+商业媒体
施普林格科学+商业媒体（Springer Science+Business Media）或施普林格（Springer，），在柏林成立，是一个总部位于德国的世界性出版公司，它出版教科书、学术参考书以及同行评论性杂志，专--于科学、技术、数学以及医学领域。在科学、技术与医学领域中，施普林格是最大的书籍出版者，以及第二大世界性杂志出版者（最大的是爱思唯尔）。施普林格拥有超过60个出版社，每年出版1,900种杂志，5,500种新书，营业额为9.24亿欧元（2006年），雇有超过5,000名员工 。施普林格在柏林、海德堡、多德雷赫特（位于荷兰）与纽约设有主办事处。施普林格亚洲总部设在香港。2005年8月，施普林格在北京成立代表处。.
新！!: 邱奇－图灵论题和施普林格科学+商业媒体 · 查看更多 »
重定向到这里：
Church-Turing论题，丘奇-图灵论题，丘奇－图灵论题。
