我读过"什么是图灵完整"和维基百科页面,但我对正式证据不太感兴趣,而不是图灵完全的实际意义.
我实际上要确定的是,我刚刚设计的玩具语言是否可以用作通用语言.我知道我可以证明我是否可以用它来编写图灵机.但是,在我确信成功之前,我不想进行这项运动.
有没有最低限度的功能,没有图灵完整性是不可能的？是否有一系列功能几乎可以保证完整性？
(我的猜测是条件分支和可读/可写的内存存储将使我的大部分方式)
编辑:
我想我已经说过"图灵完成"了.我试图以合理的信心猜测具有特定功能集的新发明的语言(或者具有特定指令集的VM)将能够计算任何值得计算的东西.我知道证明你可以用它建立图灵机是一种方式,但不是唯一的方法.
我所期待的是一套类似的准则:"如果可以做X,Y和Z,它可以或许做任何事情".
什么是所需的最小原语集,以便语言是图灵完整的和lisp变体？
看起来像汽车,cdr和一些流量控制和REPL的东西就足够了.如果有这样的清单那就好了.
假设只有3种类型的数据,整数,符号和列表.(如在picolisp中)