是SQL甚至TSQL图灵完成？
这是今天在办公室出现的。 我没有计划做这样的事情，但理论上你可以在SQL中编写一个编译器吗？ 乍一看，在我看来，图灵是完整的，尽pipe对于许多类问题来说非常麻烦。
如果它不是完整的，那要做什么呢？
注意：我不想做任何事情，比如在SQL中编写一个编译器，我知道这将是一个愚蠢的事情，所以如果我们可以避免这个讨论，我将不胜感激。
事实certificate，即使没有真正的“脚本”扩展，比如PL / SQL或PSM（它们被devise成真正的编程语言，所以这样做有点作弊），SQL也可能是Turing Complete。
在这组幻灯片中， Andrew Gierthcertificate了使用CTE和Windowing SQL是Turing Complete，通过构build循环标签系统 ，这已经被certificate是Turing Complete。 然而，CTEfunction是重要的部分 – 它允许您创build可以引用自己的命名子expression式，从而recursion地解决问题。
有趣的是，CTE并没有被真正添加到把SQL转换成一种编程语言 – 只是把一个声明式查询语言转变成一个更强大的声明式查询语言。 就像在C ++中那样，尽pipe它们并不打算创build元编程语言，但其模板却是图灵完备的。
哦， 在SQL例子中的Mandelbrot是非常令人印象深刻的，以及:)
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是一个，但也是例如HTML。 这个定义比较含糊，这是一个毫无意义的争论点。
TSQL是图灵完成。为了certificate我做了一个BrainFuck解释器。
SQL中的BrainFuck解释器 – 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 backward 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 严格地说，SQL现在是一种完全的语言，因为最新的SQL标准包括“持久存储模块”（PSMs）。 简而言之，PSM是Oracle中的PL / SQL语言的标准版本（以及其他类似的当前DBMS的程序扩展）。
随着这些PSM的包含，SQL变得完整
ANSI最初在SQL-86中定义的select语句不是完整的，因为它总是终止的（除了recursionCTE，并且只有当实现支持任意深recursion时）。 因此不可能模拟任何其他的图灵机。 存储过程是完整的，但那是作弊;-)
