有点出乎意料

【 在 hgoldfish 的大作中提到: 】
: https://arxiv.org/pdf/1605.05274.pdf
--
FROM 111.18.36.*

实现一个小语言就行了。比如实现递归和分支，或者实现跳转和分支，等价的很多。
【 在 littleSram 的大作中提到: 】
: 图灵完备究竟怎么验证呢，一直不清楚
:
: 【 在 hgoldfish 的大作中提到: 】
: ...................
--
FROM 114.249.196.*

图灵可计算性是可计算性理论的基础知识。原始定义是能实现任意图灵机（一个有限状态无限外存储的机器），等价的计算模型形式很多，最著名的就是基于递归函数的lambda演算。比较接近现实编程语言的模型是各种寄存器机器，其中最精简的版本只要求实现无界整数类型寄存器赋值，加一运算，je 条件跳转（if x=y goto）三条指令。后来的 goto 有害论的理论基础是 if 结构和 while 循环结构计算能力和包含 goto 的语言相同，其实也是在说计算模型等价性。
所以要证明图灵完全其实要求不高，写理论论文一般还会忽略现实语言中变量取值范围有限、可用存储有限之类限制。现实中图灵完全的东西不一定能高效完成任意运算。

我扫了一下这个论文，他们主要是利用 java 里对泛型类型参数的子类型约束，类似
static <T> int binarySearch( List<? extends Comparable<? super T>> list, T key) { /* ...*/ }
这种语法，构造复杂的子类型关系实现了一套运算，完成图灵机模型构造。
所以这东西和 C++ 的模板和宏不一样，对现实的元编程没多大实用价值。只有一些理论意义，比方说理论上 Java 编译器的停机问题是不可判定的，你可以写一个合法 java 程序把编译器搞死——这种体验对 C++ 就很常见了。
【 在 littleSram 的大作中提到: 】
: 只要有递归和分支就是图灵完备的么？
: 小语言我实现过minilisp，支持if，while，cons，cdr，car，也支持宏和闭包。八皇后问题可以求解。
: 但是我不知道是不是图灵完备的。
: ...................
--
FROM 114.249.196.*

谢谢，有太多概念不理解。。。
【 在 milksea 的大作中提到: 】
: 图灵可计算性是可计算性理论的基础知识。原始定义是能实现任意图灵机（一个有限状态无限外存储的机器），等价的计算模型形式很多，最著名的就是基于递归函数的lambda演算。比较接近现实编程语言的模型是各种寄存器机器，其中最精简的版本只要求实现无界整数类型寄存器赋值，加一运算，je 条件跳转（if x=y goto）三条指令。后来的 goto 有害论的理论基础是 if 结构和 while 循环结构计算能力和包含 goto 的语言相同，其实也是在说计算模型等价性。
: 所以要证明图灵完全其实要求不高，写理论论文一般还会忽略现实语言中变量取值范围有限、可用存储有限之类限制。现实中图灵完全的东西不一定能高效完成任意运算。
: 我扫了一下这个论文，他们主要是利用 java 里对泛型类型参数的子类型约束，类似
: ...................
--
FROM 114.249.19.*

但c++的模板可以做元编程，java这个做元编程还是极不合适
【 在 hongdiao 的大作中提到: 】
: 图灵完备听起来高大上，其实要求不高。 C++模板当初设计的时候其实主要是考虑的是泛型，结果无意中也达到了图灵完备，以至于现在发展出了模板元编程这么妖的东西。
: --
: FROM 1.91.32.*
--
FROM 124.64.17.*