SQL 또는 TSQL Turing이 완료 되었습니까?

SQL 또는 TSQL Turing이 완료 되었습니까?

---

이것은 오늘 사무실에서 나타났습니다. 나는 그런 일을 할 계획이 없지만 이론적으로 SQL로 컴파일러를 작성할 수 있습니까? 언뜻보기에 튜링이 완료 된 것처럼 보였지만 많은 클래스의 문제에는 매우 번거 롭습니다.

튜링이 완료되지 않았다면 무엇이 필요합니까?

참고 : SQL에서 컴파일러를 작성하는 것과 같은 일을하고 싶지는 않습니다. 어리석은 일이라는 것을 알고 있으므로 그러한 토론을 피할 수 있다면 감사하겠습니다.

---

PL / SQL 또는 PSM (진정한 프로그래밍 언어로 설계되었으므로 일종의 부정 행위 임)과 같은 진정한 '스크립트'확장 없이도 SQL이 튜링 완료 될 수 있습니다.

에서 슬라이드 세트 앤드류 Gierth은 CTE와 윈도우 화 SQL은 구성하여, 튜링과 증명 순환 태그 시스템 전체 튜링 것으로 판명되었습니다. 그러나 CTE 기능은 중요한 부분입니다. 즉, 자신을 참조 할 수있는 명명 된 하위 표현식을 작성하여 문제를 재귀 적으로 해결할 수 있습니다.

흥미로운 점은 CTE가 실제로 SQL을 프로그래밍 언어로 바꾸기 위해 추가 된 것이 아니라 선언적 쿼리 언어를보다 강력한 선언적 쿼리 언어로 바꾸는 것입니다. 메타 프로그래밍 언어를 만들려는 의도는 아니지만 템플릿이 튜링 완료된 C ++과 비슷합니다.

오, SQL 예제 에서 설정된 Mandelbrot 는 매우 인상적입니다. :)

---

주어진 프로그래밍 언어는 계산적으로 Turing 머신과 동등한 것으로 보일 수 있으면 Turing-complete라고합니다.

TSQL에서 BrainFuck 인터프리터를 만들 수 있기 때문에 TSQL은 Turing Complete 입니다.

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 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

---

http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question/

이 주제에 대한 토론입니다. 인용문 :

이와 같은 SQL (즉, SQL92 표준)은 튜링 완료되지 않습니다. 그러나 Oracle의 PL / SQL 및 SQL Server의 T-SQL과 같은 SQL에서 파생 된 많은 언어가 완전히 완성되었습니다.

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.

---

Strictly speaking, SQL is now a turing complete language because the latest SQL standard includes the "Persistent Stored Modules" (PSMs). In short, a PSM is the standard version of the PL/SQL language in Oracle (and other similar procedural extensions of current DBMS).

With the inclusion of these PSMs, SQL became turing complete

---

An ANSI select statement, as originally defined in SQL-86, is not turing complete because it always terminates (except for recursive CTEs and only if the implementation supports arbitrarily deep recursion). It is therefore not possible to simulate any other turing machine. Stored procedures are turing complete but thats cheating ;-)

참고URL : https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete