看完这个问题后,CSS图灵完成了吗？- 它收到了一些深思熟虑的简洁答案 - 它让我想知道:HTML图灵是否完整？
虽然简短的答案是肯定的肯定或否定,但也请提供一个简短的描述或反例来证明HTML是否是图灵完全(显然不能同时).关于其他版本的HTML的信息可能很有趣,但正确的答案应该回答HTML5.
我的理解是,这意味着可以编写一个程序来正式证明用静态类型语言编写的程序将没有某些(小)缺陷子集.
我的问题如下:
假设我们有两种图灵完整语言,A和B.A被认为是'类型安全'而'B'被假定为不是.假设我有一个程序L来检查用A写的任何程序的正确性.什么阻止我将用B写的任何程序翻译成A,应用L.如果P从A转换为B,那么为什么不是PL a用B编写的任何程序的有效类型检查器？
我接受过代数培训,而且我才刚开始学习CS,所以可能有一些明显的原因,这不起作用,但我非常想知道.整个'类型安全'的东西已经有一段时间闻到了我的味道.
我最近发现了这个：https : //github.com/xoreaxeaxeax/movfuscator
这似乎取决于mov图灵完备的事实。这是真的吗，为什么？
暂停问题对于图灵完整语言是无法解决的,并且对于一些非TC语言(例如它总是停止的正则表达式),它可以简单地解决.
我想知道是否有任何语言都具有停止和不停止的能力,但允许一种算法可以确定它是否停止.
我花了一两个星期编写一个简单的逻辑解算器.构建它之后,我发现自己想知道它所解决的语言是否是图灵完备的.因此,我编写了一小组方程式,它们接受SKI组合子演算中的任何有效表达式,并生成包含该表达式的正常形式的结果集.由于SKI 是 Turing-complete,证明我的语言可以执行SKI将证明其图灵完整性.
然而,有一个小故障.解算器不会按正常顺序减少表达式.实际上它的作用是尝试每一个可能的减少订单.这意味着解决方案集通常很大.如果存在正常形式,它将存在于某处,但很难分辨到哪里.
这让我有两个问题:
我的语言图灵完整吗？或者我需要找到更好的证据吗？
解决方案的数量是输入的可计算函数吗？
(起初我假设解决方案集的大小在输入大小中是指数或因子.但仔细观察,这不是真的.你可以编写已经处于正常形式的巨大表达式,以及不终止的小表达式我有一种感觉,确定解决方案集的大小可能等于解决停机问题,但我不完全确定......)
正则表达式通常被指向不完全转换的语言的经典示例.例如,"正则表达式"作为这个SO问题的答案给出,寻找不是图灵完整的语言.
在我的,或许有点基本的,理解转向完整性的概念,这意味着不能使用正则表达式检查"平衡"的模式.平衡意义具有与结束字符相同数量的开始字符.这是因为要做到这一点需要你有某种状态,以允许你匹配开始和结束字符.
然而,正则表达式的.NET实现引入了平衡组的概念.此构造旨在让您回溯并查看先前的组是否匹配.这意味着.NET正则表达式:
^(?<p>a)*(?<-p>b)*(?(p)(?!))$
可以匹配以下模式:
ab
aabb
aaabbb
aaaabbbb
... etc. ...
这是否意味着.NET的正则表达式是图灵完成的？或者还有其他缺少的东西,这些语言需要图灵完成吗？
你如何争论lambda演算是图灵完整的事实(以最简单的方式)？
例如,在编写无法用图灵完整语言完成的操作系统时是否存在某些问题？
language-agnostic compiler-construction programming-languages language-theory turing-complete
我一直在网上搜索,我发现有些矛盾的答案.一些消息来源声称,语言/机器/什么具备的,你是图灵完备当且仅当它有两个有条件和无条件分支(我的猜测是一种多余的),有的说只有无条件的要求,别人只有条件是必须的.
德国Z3(显示于1941年5月工作)由Konrad Zuse设计.它是第一台通用型数字计算机,但它是机电式的,而不是电子的,因为它使用了继电器用于所有功能.它使用二进制数学逻辑计算.它可以通过穿孔带编程,但缺少条件分支.虽然不是为图灵完整性而设计的,但它偶然发生在1998年(但为了利用这种图灵完整性,复杂,聪明的黑客是必要的).
究竟是什么复杂,聪明的黑客？
R. Rojas撰写的1998年论文摘要也指出(请注意,我没有读过这篇论文,它只是IEEE的一个片段.):
由Konrad Zuse在1938年至1941年之间建造的计算机器Z3可以仅执行在穿孔带中编码的浮点算术运算(加法,减法,乘法,除法和平方根)的固定序列.从计算历史的角度来看,一个有趣的问题是这些操作是否足以进行通用计算.该论文表明,实际上,包含这些算术指令的单个程序循环可以模拟其磁带具有给定有限大小的任何图灵机.这是通过纯粹的算术方法模拟条件分支和间接寻址来完成的.因此,Zuse的Z3至少在原则上与今天具有有限寻址空间的计算机一样普遍.
简而言之,SOers,Turing-completeness究竟需要什么类型的分支？假设无限的内存,只有一个goto或jmp分支结构(没有if或jnz构造)的语言可以被认为是图灵完备吗？