评估语言的“转换完整性"的实用准则是什么? [英] What are practical guidelines for evaluating a language's "Turing Completeness"?

问题描述

我已阅读"what-is-turing-complete" 和维基百科页面，但我对正式证明的兴趣不如对图灵完成的实际意义感兴趣.

I've read "what-is-turing-complete" and the wikipedia page, but I'm less interested in a formal proof than in the practical implications of being Turing Complete.

我实际上要确定的是，我刚刚设计的玩具语言是否可以用作通用语言.我知道我可以证明是否可以用它编写图灵机.但是在我相当确定成功之前，我不希望进行该练习.

What I'm actually trying to decide is if the toy language I've just designed could be used as a general-purpose language. I know I can prove it is if I can write a Turing machine with it. But I don't want to go through that exercise until I'm fairly certain of success.

是否有最少的功能集，没有这些功能，图灵完整性是不可能的? 是否有实际上可以保证完整性的一组功能?

Is there a minimum set of features without which Turing Completeness is impossible? Is there a set of features which virtually guarantees completeness?

(我的猜测是条件分支和可读/可写内存存储将带给我大部分帮助)

我想我已经说完成"了.我试图以合理的信心猜测具有特定功能集的新发明的语言(或者具有特定指令集的VM)将能够计算出任何值得计算的东西.我知道证明您可以用它构建图灵机是一种方法，但不是唯一的方法.

I think I've gone off on a tangent by saying "Turing Complete". I'm trying to guess with reasonable confidence that a newly invented language with a certain feature set (or alternately, a VM with a certain instruction set) would be able to compute anything worth computing. I know proving you can build a Turing machine with it is one way, but not the only way.

我所希望的是一组准则，例如:如果它可以执行X，Y和Z，则它可以可能执行任何操作".

What I was hoping for was a set of guidelines like: "if it can do X,Y,and Z, it can probably do anything".

推荐答案

您需要某种形式的动态分配构造(malloc或new或cons可以使用)以及递归函数或其他某种编写方式一个无限循环.如果您有这些东西，并且可以做任何有趣的事情，那么您几乎可以肯定是图灵完备的.

You need some form of dynamic allocation construct (malloc ornew or cons will do) and either recursive functions or some other way of writing an infinite loop. If you have those and can do anything at all interesting, you're almost certainly Turing-complete.

lambda演算的功能与Turing机器相当，并且如果实现lambda演算，编写lambda演算程序实际上非常有趣. 方法比为Turing机器编写程序更有趣！

The lambda calculus is equivalent in power to a Turing machine, and if you implement lambda calculus it is actually pretty fun writing lambda calculus programs. Way more fun than writing program for a Turing machine!

我知道的图灵完整性的唯一实际含义是，您可以编写不终止的程序.我使用了几种特殊的语言来保证终止，因此不是图灵完备的.有时，放弃额外的表达能力以换取有保证的终止是有用的.

The only practical implication of Turing-completeness I'm aware of is that you can write programs that don't terminate. I've used a couple of special-purpose languages that guarantee termination and therefore are not Turing-complete. Sometimes it is useful to give up the extra expressive power in exchange for guaranteed termination.

这篇关于评估语言的“转换完整性"的实用准则是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！