标签: turing-machines

我正在尝试学习与编程语言相关的Chomsky Hierarchy的某些方面,我仍然需要阅读Dragon Book.

我读过大多数编程语言都可以解析为无上下文语法(CFG).就计算能力而言,它等于下推非确定性自动机之一.我对吗？

如果这是真的,那么CFG怎么能保持一个不受限制的语法(UG),这是完整的？我问,因为即使编程语言由CFG描述,它们实际上也用于描述图灵机,所以通过UG.

我认为这是因为至少有两个不同的计算级别,第一个,即CFG的解析侧重于与语言结构(表示？)相关的语法,而另一个侧重于语义(意义,解释)数据本身？)与编程语言的功能有关,这是完整的.再次,这些假设是对的吗？

当我正在研究图灵机和PDA时,我认为第一台计算设备是图灵机.

因此,我认为存在一种称为图灵机的实用机器,其状态可以用一些特殊设备(比如触发器)来表示,它可以接受磁带中的输入.

因此我怀疑如何在磁带中表示输入字符串？.但是通过答案和我书中给出的细节,我才知道图灵机是一些假设的东西.

我的问题是,图灵机如何实际实施？例如,它如何用于检查当前处理器中的拼写错误.

图灵机是否已过时？还是他们还在使用？

有没有人知道任何论文,文本或其他文件讨论使用超图来实现或代表一个不确定的图灵机？它们实际上是等同的吗？

例如,我非常确定超图能够正确且完整地表示非确定性图灵机的状态转换.但到目前为止,我还没有找到任何可以验证这一点的印刷品.在我看来,这似乎是一种如此明显的关系,但事实上,我没有找到现有的艺术,这让我觉得我走错了路.(也可能是我发现的东西不足以让我理解它在说什么.);-)

为什么我要问:我正在开发一个开源软件包,它在对等网络中进行分布式数据存储和分布式计算.我正在寻找可能支持所需功能的最原始的数据结构.到目前为止,分布式超图看起来很有希望.我的理由是,如果超图可以支持像非确定性图灵机一样通用的东西,那么它应该能够支持更高级别的图灵完整DSL.(还有其他原因,"非确定性"部分也可能对我有价值,与分布式数据和/或计算结果的版本控制有关.尽管这里试图避免论文.)

部分答案:

• opencog人员对超图如何适应不同的计算模型进行了深入的讨论; 这显然与HypergraphDB软件包的开发有关:http: //markmail.org/message/5oiv3qmoexvo4v5j
• 在MathOverflow上,有一个问题讨论超图可以做什么 - 还没有提到图灵,但我要添加它:https: //mathoverflow.net/questions/13750/what-are-the-applications-of -hypergraphs
• 如果超图可以代表一个不确定的图灵机,那么我认为带有加权边的超图将等同于一个概率图灵机. http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

一些程序员认为理论CS课程(特别是我的学生)并没有多大意义.这是我发现非常相关的东西.让我为那些以前没见过的人制作碎片......

A)编程问题可以重写为有关语言的问题.

B)图灵机识别语言.

C)图灵机可以编码为(大)整数.

D)因此,可能的图灵机的数量是无穷无尽的

E)集合的幂集只是该集合的所有可能子集.

F)如果一个集合是无数的,它的功率集更大,即无数无限.

G)因此,如果一种语言是无限的,它就有无数无数的子集.这些都代表了一个问题.但是,只有很多图灵机可以用来解决这些问题.如果我们无法解决图灵机的问题,就无法解决.

结论......我们只能解决所有问题的无限小部分.

我的问题几乎就在这里......

每当我向学生提出这个论点时,他们就会陷入可数与无数无限之间.他们通常没有很强的数学背景,所以试图通过康托尔的对角化论证来解释他们的眼睛.

通常我试着给他们一些他们可以抓住的东西,比如这样......在计数数字线的任何部分放置一个有限的盒子,我们捕获有限数量的那些数字......但是在有限的数量上放置一个有限的盒子.实数行,我们捕获无限数量的实数.一种证据表明存在的实数比计数数字多.

最后我的问题......你如何向那些从未听过这个概念的人解释多层次无穷大的概念,可能不是数学倾向的？

最终编辑:我通过提出这个问题了解了很多,并且我很感激反馈.我浪费了太多时间试图找出"社区维基"究竟是什么.我了解到,有些人反对理论问题存在固有的偏见,我认为这只是一个错误,因为我们今天做的很多事情都是昨天的理论.但这种偏见是自然的,虽然我不同意理论的价值,但我对它没有任何问题,这有助于我理解我的学生来自哪里.我认为BS评论是不必要的.

我觉得这个问题根本不是一个民意调查或一个2009年的问题.那些只想要编码问题和编码答案的人可能想重新审视这个要求.我已将此问题移至社区维基,但强烈认为我不得不通过不当使用武力来这样做.

正则表达式通常被指向不完全转换的语言的经典示例.例如,"正则表达式"作为这个SO问题的答案给出,寻找不是图灵完整的语言.

在我的,或许有点基本的,理解转向完整性的概念,这意味着不能使用正则表达式检查"平衡"的模式.平衡意义具有与结束字符相同数量的开始字符.这是因为要做到这一点需要你有某种状态,以允许你匹配开始和结束字符.

然而,正则表达式的.NET实现引入了平衡组的概念.此构造旨在让您回溯并查看先前的组是否匹配.这意味着.NET正则表达式:

^(?<p>a)*(?<-p>b)*(?(p)(?!))$

可以匹配以下模式:

ab
aabb
aaabbb
aaaabbbb
... etc. ...

这是否意味着.NET的正则表达式是图灵完成的？或者还有其他缺少的东西,这些语言需要图灵完成吗？

我必须确定一种语言(例如L = {a ^ nb ^ mc ^ s | 0 <= n <= m <= s})是否是常规的,无上下文的,递归的,递归可枚举的或者都不是.

我知道如何确定一个语言是正规(找到DFA或正则表达式的工作)或上下文(找到一个PDA或上下文无关文法的作品); 我知道递归语言有一个总是停止的图灵机器,并且一个递归可枚举的语言有一个可能不会停止的图灵机.

所以问题是:是否有一个快速的标准来确定语言是递归还是递归可枚举或两者都没有？例如,我不需要构建一个PDA来理解语言是无上下文的,我不能通过它需要一个堆栈来看待它; 有没有类似的快速解决问题的方法(希望能省去构建图灵机的麻烦)？

你如何争论lambda演算是图灵完整的事实(以最简单的方式)？

我正在尝试围绕 lambda 演算，以及它与语言、编译器和二进制代码的关系。lambda 演算等同于图灵机的实际含义是什么，它实际上在哪里表现出来？

我不明白 lambda 演算如何取代图灵机作为计算的理论模型。图灵机是关于改变状态的顺序指令，lambda 演算是关于对某些东西进行评估的表达式。它更抽象，就像它自己的编程语言，而不是如何实际计算某些东西、使事情发生的模型。或者让我们这样说：lambda 演算就像路线图，而图灵机就像汽车模型。这两个如何被认为是等价的？是否有可能在不实施图灵机的情况下在硬件上运行软件？

例如，lisp 编译器和语言如何与 lambda 演算相关？lambda演算在哪一层实现？就 lambda 演算的定义而言，实现是否纯粹？lambda 演算背后的理论在哪里以及如何将语法转换为正在运行的二进制文件？例如，在 lambda 演算中，数字被编码为应用于其他函数 n 次的特殊函数。然而在语法上，我们使用数字文字。所有这些公理在哪里使用？

我之前正在讨论状态机,并且有一个问题是它是否可能不会停止某些输入.这似乎是国家机器的一个重要且经常被提及的属性,但我不能为我的生活弄清楚该属性的名称是什么.有这样一个词吗？它是"可停止的","不是无限循环",还是其他什么？

这些天我一直在研究NP问题,计算复杂性和理论.我相信我终于掌握了图灵机的概念,但我有一些疑惑.

我可以接受一个非确定性的图灵机有几个选项,可以为给定的状态和符号读取做什么,它总是会选择最佳选项,如维基百科所述

NTM如何"知道"它应该采取哪些行动？有两种方式可以看待它.一个是说机器是"最幸运的猜测者"; 如果存在这样的转变,它总会选择最终导致接受状态的过渡.另一种是想象机器"分支"成许多副本,每个副本都遵循一个可能的过渡.虽然DTM具有它遵循的单个"计算路径",但NTM具有"计算树".如果树的任何分支以"接受"条件停止,我们说NTM接受输入.

我无法理解的是,既然这是一个虚构的机器,我们从多数时间内解决NP问题得到什么呢？我的意思是,我还可以理解一个解决O(1)中NP问题的神奇机器,如果它可能永远不会存在,我会从中获得什么？

提前致谢.