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

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

SQL as such (i.e. the SQL92 standard) is not turing complete. However, many of the languages derived from SQL, such as Oracle's PL/SQL and SQL Server's T-SQL and others are turing complete. PL/SQL and T-SQL certainly qualify as programming languages, whether SQL92 itself qualifies is open for debate. Some people claim that any piece of code that tells a computer what to do qualifies as a programming language; by that definition SQL92 is one, but so is e.g. HTML. The definition is rather vague, and it's imo a pointless thing to argue about.

严格地说，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

甲骨文的PLSQL和微软的TSQL都是图灵完备的。 Oracle的select语句本身也是图灵完成的。

简单地，执行这个查询:

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是图灵完备的。

That's because it has affordances for branching choices ("CASE IF THEN"), and because even in SQL dialects that restrict recursion, it's trivial to write output to a table and re-read it in a subsequent query as though it were a memory register. Therefore, you can implement an interpreter for an assembly language in SQL without thinking very hard about it. If you want to demonstrate this with a minimum of labor, implement a single-instruction-set computer with an operation like 'subleq' (see https://en.wikipedia.org/wiki/One-instruction_set_computer ).

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

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

假设您有一个受执行限制的“非”图灵完整SQL解释器，这种解释器只允许您一次运行单个查询或更新操作，并对该查询施加限制。 现在，假设您可以从shell调用该解释器。 最后，假设您在命令上方键入“while true:”来在shell中执行这个SQL解释器。现在你有了图灵完全执行。

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

Non-Turing Complete languages in widespread use tend to describe "inert" data artifacts, and lack affordances for branching paths or explicit procedure invocations. Simply put, if a language has no "verbs" and/or no equivalent to "if then else", you can be sure it's Non-Turing Complete. Examples include interface definition languages (DIANA IDL, CORBA, Proto, Thrift, JSON Typedef, Coral, Ion, etc.), markup languages (XML, HTML, Markdown), data representation languages (JSON, text-format protocol buffers, ascii DIANA representation), and so on.

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

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

继续分发藏物。

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