Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
165 lines (150 sloc) 13.2 KB
--- ==> Blog post on http://lbreddemann.org/is-sap-hana-sql-sqlscript-turing-complete/
--- Original Q&A https://answers.sap.com/questions/419209/are-sqlscript-and-hana-sql-turing-complete.html
--- some links I found during research for this:
--- https://stackoverflow.com/questions/7284/what-is-turing-complete#7320
--- https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete
--- http://assets.en.oreilly.com/1/event/27/High%20Performance%20SQL%20with%20PostgreSQL%20Presentation.pdf
--- https://en.wikipedia.org/wiki/Tag_system#Cyclic_tag_systems
select current_timestamp, * from m_database;
/*
CURRENT_TIMESTAMP SYSTEM_ID DATABASE_NAME HOST START_TIME VERSION USAGE
2018-02-01 11:32:07.735 S12 S12 skullbox 2018-02-01 11:23:47.15 1.00.122.13.1507793622 CUSTOM
*/
do begin
declare prods VARCHAR(4) ARRAY;
declare currProd, initWord, currWord VARCHAR(300); -- 300 is arbitrary and would be exceeded for more runs
declare currProdNo integer = 0;
declare runs, maxruns bigint = 0;
initWord :='11001'; -- the starting/initial 'word'
maxruns := 100; -- a limit to the number of iterations
-- rule 110 is suspected to run indefinitively
prods = ARRAY ('010', '000', '1111'); -- the three 'producer rules' stored in a string array
currWord := :initWord;
runs := 0;
-- dummy table var to monitor output
tmp = select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD
from dummy;
while (:runs < :maxruns) DO
runs := :runs+1;
currProdNo := mod(:runs,3)+1; -- pick rule no. 1,2 or 3 but never 0
-- as SQLScript arrays are 1 based
currProd := :prods[:currProdNo];
if (left (:currWord, 1)='1') then -- add current producer to the 'word'
currWord := :currWord || :currProd;
end if;
currWord := substring (:currWord, 2); -- remove leftmost character
-- save current state into temp table var
tmp = select RUNS, CURRPROD, CURRWORD from :tmp
union all
select :runs as RUNS, :currProd as CURRPROD, :currWord as CURRWORD
from dummy;
end while;
select * from :tmp; -- output the table var
end;
/*
Statement 'do begin declare prods VARCHAR(4) ARRAY; declare currProd, initWord, currWord VARCHAR(300); declare ...'
successfully executed in 717 ms 39 µs (server processing time: 715 ms 590 µs)
Fetched 101 row(s) in 2 ms 517 µs (server processing time: 0 ms 424 µs)
RUNS CURRPROD CURRWORD
0 ? 11001
1 000 1001000
2 1111 0010001111
3 010 010001111
4 000 10001111
5 1111 00011111111
6 010 0011111111
7 000 011111111
8 1111 11111111
9 010 1111111010
10 000 111111010000
11 1111 111110100001111
12 010 11110100001111010
13 000 1110100001111010000
14 1111 1101000011110100001111
15 010 101000011110100001111010
16 000 01000011110100001111010000
17 1111 1000011110100001111010000
18 010 000011110100001111010000010
19 000 00011110100001111010000010
20 1111 0011110100001111010000010
21 010 011110100001111010000010
22 000 11110100001111010000010
23 1111 11101000011110100000101111
24 010 1101000011110100000101111010
25 000 101000011110100000101111010000
26 1111 010000111101000001011110100001111
27 010 10000111101000001011110100001111
28 000 0000111101000001011110100001111000
29 1111 000111101000001011110100001111000
30 010 00111101000001011110100001111000
31 000 0111101000001011110100001111000
32 1111 111101000001011110100001111000
33 010 11101000001011110100001111000010
34 000 1101000001011110100001111000010000
35 1111 1010000010111101000011110000100001111
36 010 010000010111101000011110000100001111010
37 000 10000010111101000011110000100001111010
38 1111 00000101111010000111100001000011110101111
39 010 0000101111010000111100001000011110101111
40 000 000101111010000111100001000011110101111
41 1111 00101111010000111100001000011110101111
42 010 0101111010000111100001000011110101111
43 000 101111010000111100001000011110101111
44 1111 011110100001111000010000111101011111111
45 010 11110100001111000010000111101011111111
46 000 1110100001111000010000111101011111111000
47 1111 1101000011110000100001111010111111110001111
48 010 101000011110000100001111010111111110001111010
49 000 01000011110000100001111010111111110001111010000
50 1111 1000011110000100001111010111111110001111010000
51 010 000011110000100001111010111111110001111010000010
52 000 00011110000100001111010111111110001111010000010
53 1111 0011110000100001111010111111110001111010000010
54 010 011110000100001111010111111110001111010000010
55 000 11110000100001111010111111110001111010000010
56 1111 11100001000011110101111111100011110100000101111
57 010 1100001000011110101111111100011110100000101111010
58 000 100001000011110101111111100011110100000101111010000
59 1111 000010000111101011111111000111101000001011110100001111
60 010 00010000111101011111111000111101000001011110100001111
61 000 0010000111101011111111000111101000001011110100001111
62 1111 010000111101011111111000111101000001011110100001111
63 010 10000111101011111111000111101000001011110100001111
64 000 0000111101011111111000111101000001011110100001111000
65 1111 000111101011111111000111101000001011110100001111000
66 010 00111101011111111000111101000001011110100001111000
67 000 0111101011111111000111101000001011110100001111000
68 1111 111101011111111000111101000001011110100001111000
69 010 11101011111111000111101000001011110100001111000010
70 000 1101011111111000111101000001011110100001111000010000
71 1111 1010111111110001111010000010111101000011110000100001111
72 010 010111111110001111010000010111101000011110000100001111010
73 000 10111111110001111010000010111101000011110000100001111010
74 1111 01111111100011110100000101111010000111100001000011110101111
75 010 1111111100011110100000101111010000111100001000011110101111
76 000 111111100011110100000101111010000111100001000011110101111000
77 1111 111111000111101000001011110100001111000010000111101011110001111
78 010 11111000111101000001011110100001111000010000111101011110001111010
79 000 1111000111101000001011110100001111000010000111101011110001111010000
80 1111 1110001111010000010111101000011110000100001111010111100011110100001111
81 010 110001111010000010111101000011110000100001111010111100011110100001111010
82 000 10001111010000010111101000011110000100001111010111100011110100001111010000
83 1111 00011110100000101111010000111100001000011110101111000111101000011110100001111
84 010 0011110100000101111010000111100001000011110101111000111101000011110100001111
85 000 011110100000101111010000111100001000011110101111000111101000011110100001111
86 1111 11110100000101111010000111100001000011110101111000111101000011110100001111
87 010 1110100000101111010000111100001000011110101111000111101000011110100001111010
88 000 110100000101111010000111100001000011110101111000111101000011110100001111010000
89 1111 101000001011110100001111000010000111101011110001111010000111101000011110100001111
90 010 01000001011110100001111000010000111101011110001111010000111101000011110100001111010
91 000 1000001011110100001111000010000111101011110001111010000111101000011110100001111010
92 1111 0000010111101000011110000100001111010111100011110100001111010000111101000011110101111
93 010 000010111101000011110000100001111010111100011110100001111010000111101000011110101111
94 000 00010111101000011110000100001111010111100011110100001111010000111101000011110101111
95 1111 0010111101000011110000100001111010111100011110100001111010000111101000011110101111
96 010 010111101000011110000100001111010111100011110100001111010000111101000011110101111
97 000 10111101000011110000100001111010111100011110100001111010000111101000011110101111
98 1111 01111010000111100001000011110101111000111101000011110100001111010000111101011111111
99 010 1111010000111100001000011110101111000111101000011110100001111010000111101011111111
100 000 111010000111100001000011110101111000111101000011110100001111010000111101011111111000
*/