SQL或者TSQL是图灵完备的吗?

https://web.archive.org/web/20110807062050/http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question

是关于这个话题的讨论。引用:

SQL本身(即SQL92标准)不是图灵完备的。然而, 许多语言源自SQL，如Oracle的PL/SQL和

. SQL Server的T-SQL和其他图灵完备 PL/SQL和T-SQL当然有资格作为编程语言 SQL92本身的资格是开放的辩论。有些人声称任何 一段告诉计算机该做什么的代码被称为 编程语言;根据这个定义，SQL92是其中之一，但e.g.也是。 超文本标记语言这个定义相当模糊，在我看来是毫无意义的

严格地说，SQL现在是一种图灵完备的语言，因为最新的SQL标准包含了“持久存储模块”(psm)。简而言之，PSM是Oracle中PL/SQL语言的标准版本(以及当前DBMS的其他类似过程扩展)。

随着这些psm的加入，SQL变得图灵完备

最初在SQL-86中定义的ANSI选择语句不是图灵完全语句，因为它总是终止(除了递归cte，并且只有在实现支持任意深度递归时)。因此，不可能模拟任何其他图灵机。存储过程是图灵完整的，但这是作弊;-)

事实证明，即使没有真正的“脚本”扩展，如PL/SQL或PSM(它们被设计成真正的编程语言，所以这有点作弊)，SQL也可以是图灵完备的。

在这组幻灯片中，Andrew Gierth通过构造循环标签系统证明了CTE和Windowing SQL是图灵完备的，这已经被证明是图灵完备的。然而，CTE特性是重要的部分——它允许您创建可以引用自己的命名子表达式，从而递归地解决问题。

值得注意的有趣的事情是，添加CTE并不是为了将SQL转换为编程语言——只是为了将声明式查询语言转换为更强大的声明式查询语言。有点像c++，它的模板被证明是图灵完备的，尽管它们并不打算创建一个元编程语言。

哦，SQL中的Mandelbrot集合的例子也非常令人印象深刻:)

如果能证明一种编程语言在计算上等价于图灵机，那么它就是图灵完备的。

TSQL是图灵完备的，因为我们可以在TSQL中创建BrainFuck解释器。

BrainFuck解释器在SQL - GitHub

所提供的代码在内存中工作，不修改数据库。

-- Brain Fuck interpreter in SQL


DECLARE @Code  VARCHAR(MAX) = ', [>,] < [.<]'
DECLARE @Input VARCHAR(MAX) = '!dlroW olleH';


-- Creates a "BrainFuck" DataBase.
-- CREATE DATABASE BrainFuck;


-- Creates the Source code table
DECLARE @CodeTable TABLE (
[Id]      INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Command] CHAR(1) NOT NULL
);


-- Populate the source code into CodeTable
DECLARE @CodeLen INT = LEN(@Code);
DECLARE @CodePos INT = 0;
DECLARE @CodeChar CHAR(1);


WHILE @CodePos < @CodeLen
BEGIN
SET @CodePos  = @CodePos + 1;
SET @CodeChar = SUBSTRING(@Code, @CodePos, 1);
IF @CodeChar IN ('+', '-', '>', '<', ',', '.', '[', ']')
INSERT INTO @CodeTable ([Command]) VALUES (@CodeChar)
END


-- Creates the Input table
DECLARE @InputTable TABLE (
[Id]   INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Char] CHAR(1) NOT NULL
);


-- Populate the input text into InputTable
DECLARE @InputLen INT = LEN(@Input);
DECLARE @InputPos INT = 0;


WHILE @InputPos < @InputLen
BEGIN
SET @InputPos = @InputPos + 1;
INSERT INTO @InputTable ([Char])
VALUES (SUBSTRING(@Input, @InputPos, 1))
END


-- Creates the Output table
DECLARE @OutputTable TABLE (
[Id]   INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Char] CHAR(1) NOT NULL
);


-- Creates the Buffer table
DECLARE @BufferTable TABLE (
[Id]     INT IDENTITY(1,1) PRIMARY KEY NOT NULL,
[Memory] INT DEFAULT 0  NOT NULL
);
INSERT INTO @BufferTable ([Memory])
VALUES (0);


-- Initialization of temporary variables
DECLARE @CodeLength INT = (SELECT COUNT(*) FROM @CodeTable);
DECLARE @CodeIndex  INT = 0;
DECLARE @Pointer    INT = 1;
DECLARE @InputIndex INT = 0;
DECLARE @Command    CHAR(1);
DECLARE @Depth      INT;


-- Main calculation cycle
WHILE @CodeIndex < @CodeLength
BEGIN
-- Read the next command.
SET @CodeIndex = @CodeIndex + 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);


-- Increment the pointer.
IF @Command = '>'
BEGIN
SET @Pointer = @Pointer + 1;
IF (SELECT [Id] FROM @BufferTable WHERE [Id] = @Pointer) IS NULL
INSERT INTO @BufferTable ([Memory]) VALUES (0);
END


-- Decrement the pointer.
ELSE IF @Command = '<'
SET @Pointer = @Pointer - 1;


-- Increment the byte at the pointer.
ELSE IF @Command = '+'
UPDATE @BufferTable SET [Memory] = [Memory] + 1 WHERE [Id] = @Pointer;


-- Decrement the byte at the pointer.
ELSE IF @Command = '-'
UPDATE @BufferTable SET [Memory] = [Memory] - 1 WHERE [Id] = @Pointer;


-- Output the byte at the pointer.
ELSE IF @Command = '.'
INSERT INTO @OutputTable ([Char]) (SELECT CHAR([Memory]) FROM @BufferTable WHERE [Id] = @Pointer);


-- Input a byte and store it in the byte at the pointer.
ELSE IF @Command = ','
BEGIN
SET @InputIndex = @InputIndex + 1;
UPDATE @BufferTable SET [Memory] = COALESCE((SELECT ASCII([Char]) FROM @InputTable WHERE [Id] = @InputIndex), 0) WHERE [Id] = @Pointer;
END


-- Jump forward past the matching ] if the byte at the pointer is zero.
ELSE IF @Command = '[' AND COALESCE((SELECT [Memory] FROM @BufferTable WHERE [Id] = @Pointer), 0) = 0
BEGIN
SET @Depth = 1;
WHILE @Depth > 0
BEGIN
SET @CodeIndex = @CodeIndex + 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);
IF @Command = '[' SET @Depth = @Depth + 1;
ELSE IF @Command = ']' SET @Depth = @Depth - 1;
END
END


-- Jump backwards to the matching [ unless the byte at the pointer is zero.
ELSE IF @Command = ']' AND COALESCE((SELECT [Memory] FROM @BufferTable WHERE [Id] = @Pointer), 0) != 0
BEGIN
SET @Depth = 1;
WHILE @Depth > 0
BEGIN
SET @CodeIndex = @CodeIndex - 1;
SET @Command = (SELECT [Command] FROM @CodeTable WHERE [Id] = @CodeIndex);
IF @Command = ']' SET @Depth = @Depth + 1;
ELSE IF @Command = '[' SET @Depth = @Depth - 1;
END
END
END;


-- Collects and prints the output
DECLARE @Output VARCHAR(MAX);
SELECT @Output = COALESCE(@Output, '') + [Char]
FROM @OutputTable;


PRINT @Output;
Go

简单地，执行这个查询:

select *
from (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)
JOIN (SELECT 0 union SELECT 1)

，您将生成8位数字的前256位。 现在使用SELECT, and和or的组合，你可以编写任何8位机器

正如你所看到的，没有表涉及，只有选择，联合和连接

在我看来，图灵完成了

对于什么是图灵完备性以及什么构成了图灵完备语言，公众仍然存在很大的困惑。我写了一篇博客文章，试图澄清这些误解，也就是说，我看了一个关于超级智能计算机的电视节目，它提供了一个非常有用的类比:

https://github.com/ubuvoid/writings/blob/main/miller/miller_is_sql.md

在这个回答中，我将详细阐述SQL的情况。

实际上，我们有足够的信息粗略地看一眼就能确定SQL是图灵完备的。

这是因为它支持分支选择(“CASE IF then”)，而且即使在限制递归的SQL方言中，将输出写入表并在后续查询中重新读取它就像它是内存寄存器一样是很简单的。因此，您可以毫不费力地用SQL实现汇编语言的解释器。如果你想用最少的劳动来演示这一点，可以用'subleq'这样的操作实现一个单指令集计算机(参见https://en.wikipedia.org/wiki/One-instruction_set_computer)。

事实上，一些实现尝试沙盒执行SQL查询并没有改变语言的核心功能，它只是在这个问题上贴上了一个创可贴，即善意的“便利性”。特征往往像刀子一样锋利。

对于演示，请考虑以下内容:

• 假设您有一个限制执行的“非”图灵完整SQL解释器，这种解释器只允许您一次运行单个查询或更新操作，并对该查询施加限制。
• 现在，假设您可以从shell调用该解释器。
• 最后，假设你输入单词"当正确时:"在shell中执行此SQL解释器。现在你有了图灵完全执行。

这是一个有意义的区别吗?我认为，如果你能清楚地表达你的语言和图灵完备性之间的唯一区别是没有while循环，那么你解释图灵完备性的框架就不是特别有用。

广泛使用的非图灵完备语言倾向于描述“惰性”;数据工件，并且缺乏分支路径或显式过程调用的支持。简单地说，如果一门语言没有“动词”;和/或不等同于“;if then else"”，你可以确定它是非图灵完备的。例子包括接口定义语言(DIANA IDL、CORBA、Proto、Thrift、JSON Typedef、Coral、Ion等)、标记语言(XML、HTML、Markdown)、数据表示语言(JSON、文本格式协议缓冲区、ascii DIANA表示)等。

在软件架构的战略部分对图灵完全执行施加限制以实现关注点分离通常是有用的，而非tc语言提供了实现这些保证的简单而健壮的方法。

一个经典的例子是在HTTP或RPC请求/响应中验证JSON有效负载或其他数据工件的模式，这是一项劳动密集型且容易出错的任务，可以使用IDL和代码模板自动完成。

继续分发藏物。

(编辑2022/04/08:有趣的事实。亚马逊在上述IDL中发明了两个 ，同时还使用了Facebook发明的第三个IDL，这一点值得怀疑。请记住，接口定义语言的主要目的是定义接口，因此我希望它们有用于将一个IDL转换为另一个IDL的IDL。我的一位同事把亚马逊的软件基础设施比作巴黎的下水道。)