波斯特-图灵机（Post-图灵机）是一种特别简单类型的图灵机的“程序公式化”由下面描述的埃米爾·萊昂·波斯特（英语：Emil Post）的图灵等价的计算模型构成。波斯特的模型和图灵的模型，尽管相互之间非常类似，但却是独立开发的。图灵的论文在1936年五月出版，波斯特的论文在十月出版。波斯特-图灵机...

{\displaystyle \omega } 上的接受计算历史。如果能判定这个波斯特对应问题的实例是否有匹配的话，那图灵机是否接受输入的问题也就是可判定的了。由于图灵机的接受问题是个基本的不可判定问题，于是可以说明波斯特对应问题也同样是不可判定的。 E. L. Post. A variant of...

在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。 图灵机和邱奇－图灵论题 我们考虑关于图灵机的可计算性理论。本节中，固定字符集是{0, 1}， 0 , 1 ∗ {\displaystyle {0,1}^{*}} 是所有有限长度字符串的集合。一个语言即是...

邱奇-图灵论题（英語：Church–Turing thesis，又称邱奇-图灵猜想，邱奇论题，邱奇猜想，图灵论题）是一个关于可计算性理论的假设。该假设论述了关于函数特性的，可有效计算的函数值（用更现代的表述来说--在算法上可计算的)。简单来说，邱奇-图灵论题认为“任何在算法上可计算的问题同样可由图灵机计算”。...

FSM 可以模拟四个计数器，依次模拟两个栈，再次模拟图灵机。所以，FSM 加上两个计数器至少有图灵机一样的能力。图灵机可以轻易的模拟带有两个计数器的 FSM，所以两个机器有等价的能力。 停机问题 指针机 波斯特-图灵机 随机存取机 寄存器机 图灵机 Wang B-machine George Boolos...

1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年埃米尔·莱昂·珀斯特（英语：Emil Leon Post）的波斯特-图灵机和艾伦·图灵1937年提出的图灵机。即使在当下，依然常有符合直觉的想法难以定义为形式化算法的情况。 算法是有效方法（英语：Effective...

波斯特-图灵机模型而闻名，他在希尔伯特第十问题上的工作引出了MRDP定理。 戴维斯在希尔伯特第十问题上做出了杰出的工作，并凭借相关论述而获得了1975年勒罗伊·斯蒂尔奖、乔夫涅特奖（英语：Chauvenet Prize）（与鲁本·赫什（英语：Reuben Hersh）一起）和1974年莱斯特·福特奖（英语：Paul...

給予一個為初始點的有理坐標是週期性，決定位於basin of attraction是否開集，或是否在平分線函數迭代為兩個綱比或三個綱比。 決定Λ演算方程是否有正則形式。 黑盒 图灵机 图灵归约 交互式证明系统 隨機預言機 Stallworth, Daniel T. and Fred W. RoushAn Undecidable Property...

「用真值表製表的推理模式是由弗雷格、查尔斯·皮尔士和恩斯特·施羅德於1880年代所发明的。這種表格於1920年代之後廣泛地發現在許多文獻上（扬·武卡谢维奇、埃米爾·波斯特、维特根斯坦）”（蒯因, 39）。路易斯·卡罗早在1894年就公式化了真值表来解决特定问题，但是包含他这项工作的手稿直到1977年才被发现。维特...

这个仪式据信开始于公元前1500年代的迈锡尼时代，在两千多年间每年举行一次。在雅典的庇西特拉图治下，厄琉息斯秘仪成为了泛希腊的仪式，朝拜者从希腊各地、甚至希腊之外涌来参加。 仪式由两大家族垄断：欧墨尔波斯家族（Eumolpidae）以及克律克斯（Keryx）家族（Kerykes）。从大约前300...

的元語言（即元語言的元語言）來定義元語言的真謂詞，這樣的定義方式是永無止盡的。 這個定理算是波斯特定理（Post's theorem）在算術階層中的引理。這個定理是繼塔斯基不可定義定理發表數年後完成的。在波斯特定理的基礎下，我們可透過歸謬法給出塔斯基定理的語義證明如下：...

739磅（假） 有些命題被認為是先驗且綜合的，例如： 直线是兩點間最短的路徑（真） 3 + 4 = 8（假） 各種數學敘述 邏輯實證主義 逻辑断言 克律西波斯 Irving & Carl 2019，第4-5頁. sfn error: no target: CITEREFIrvingCarl2019 (help)...

的議題，之後的各個數學領域被合稱為數理邏輯。形式邏輯的發展和其在電腦上的應用是電腦科學的基礎。戈特弗里德·莱布尼茨、乔治·布尔、戈特洛布·弗雷格、 大卫·希尔伯特、库尔特·哥德尔，等等，都在這個過程中非常重要。 经典逻辑: 经典逻辑的逻辑系统基于公理化的传统逻辑的四个基本思维规律：同一律, 排中律,...

logic），标识已经被最深入的研究和最广泛的使用的一类演绎推理逻辑。经典逻辑是19和20世纪的创新，它比亚里士多德的传统逻辑具有更广泛的应用，并且能够将亚里士多德的传统逻辑表述为一个特例。经典逻辑满足一些公理化的基本思维规律，包括：同一律、排中律、无矛盾律（也被称为矛盾律）。 古希腊亚里斯多德的传统逻辑主要反映在其著作集《工具论》...

Mick's Gym），这个地方已由老教练米奇·戈德米尔过继给儿子，目前年久失修。会想到之前和米奇的交情，洛奇灵机一动，决定自己当教练，重新开放健身馆。 洛奇和宝利找来俄克拉荷马的年轻拳手汤米·刚恩，提出给他当教练。训练汤米的时候，洛奇突然有了目标，汤米也晋升为...