SQL is NEXP-hard with just strings, inner join, and temp tables

nexp.sql

-- our model of computation is 2-symbol, N-state Turing machines;
-- tape is represented as ...0010$1234$1110... ; $$-bracketed part
-- is _one before_ the logical head position, so the head is over a
-- "1" symbol.

create table rule(before text, after text);
insert into rule values
  ('0$123$0','$124$01'),..., -- write 1 and shift left
  ('$124$11','0$125$1'),..., -- write 0 and shift right
  ('$125$0','$$'),..., -- halt
  ('$0$','0$0$'),('$0$','$0$0'), -- initial state can create tape
  ('$$0',''),('0$$',''),('$$1',''),('1$$',''), -- cleanup after halt
  ('$$','$$'); -- once halted you are allowed to remain

-- make a table of all plausible strings of length up to 2^N
create table strings(x text);
insert into strings values (''), ('0'), ('1');

insert into strings select a.x||b.x from strings a, strings b;
-- ... N times ...
insert into strings select a.x||b.x from strings a, strings b;

-- 1-step transitions
create table trans(before text, after text);
insert into trans select left.x||rule.before||right.x,
  left.x||rule.after||right.x from rule, strings left, strings right;
-- 2^N step transitions
insert into trans select first.before, second.after from
  trans first, trans second where first.after = second.before;
-- ... N times ...
insert into trans select first.before, second.after from
  trans first, trans second where first.after = second.before;

select count(*) from trans where before = '$0$' and after = '$$';