On: `find` + `mkdir` is Turing complete

[ogiekako2]

Thank you for your comment on my article. I think I've managed to fix the proof by implementing a tag system. Would you (anyone) mind reviewing my code [1][2]? The key point is using back references, which I think gave us capabilities beyond regular expressions to achieve Turing completeness. However, I'm not very familiar with tag systems, and I'm worried I might have missed something.

[1] https://onecompiler.com/bash/42mux2442 [2] https://onecompiler.com/bash/42mux3nf8

[deredede → ogiekako2]

I am not an expert in either tag systems (or `find`), but this seems right. Using backreferences to handle copies sounds right (it does add expressive power to regular expressions but does not give Turing completeness, afaik).

I think your first example is missing the "any word of length < 2 is a halting word" condition but it is present in your second example.

[ogiekako2 → deredede]

Thank you! I've updated the article with a link to my comment.

[uzerfcwn → ogiekako2]

The definition of tag systems says "add P(x) to the end" but doesn't define x.

I can't spot errors in the logic or code, though I'm not an expert either.

[ogiekako2 → uzerfcwn]

Thank you! I have fixed the sentence and some edge case handling.