I've been playing around with this for a bit since we basically have all the core datalog logic stuff ready, and I made this thing:
output(S) :- run(S).
entry(S) :- anbncn(S), output("Accept!").
anbncn("") :- .
anbncn(S) :- abc_split(S, A, B, C), streq(A, B), streq(B, C).
streq(A, B) :- string_concat("", A, B).
charne("a", "b").
charne("a", "c").
charne("b", "c").
charne(A, B) :- charne(B, A).
abc_split(S, A, B, C) :-
count_chars(S, "a", A, BC),
count_chars(BC, "b", B, CC),
count_chars(CC, "c", C, "").
# normal route
count_chars(S, C, O, R) :-
string_concat(C, RR, S),
count_chars(RR, C, O2, R),
string_concat("1", O2, O).
# other char
count_chars(S, C, O, R) :-
charne(C, C1),
string_concat(C1, RR, S),
streq(O, ""),
streq(R, S).
# empty case
count_chars("", C, O, R) :-
streq(C, C),
streq(O, ""),
streq(R, "").
The same strategy can be used to turn any turing machine into a modus program that takes entry(S)
for some string S
, and output a docker image iff TM accept (just use the string as a tape, have something like TM(q, tape_left, tape_current, tape_right)
). This means that the claim that this language is not Turing complete in the doc repo is actually false.