`find` + `mkdir` is Turing complete

Re:`find` + `mkdir` is Turing complete by ogiekako2 on Thursday August 01, 2024 @03:54AM (#41127041)

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

[ Parent | on HN ]

Re:`find` + `mkdir` is Turing complete by deredede on Thursday August 01, 2024 @06:33AM (#41127750)

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.

[ Parent | on HN ]

Re:`find` + `mkdir` is Turing complete by ogiekako2 on Thursday August 01, 2024 @07:06AM (#41127927)

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

[ Parent | on HN ]

Re:`find` + `mkdir` is Turing complete by uzerfcwn on Friday August 02, 2024 @08:29AM (#41138289)

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.

[ Parent | on HN ]

Re:`find` + `mkdir` is Turing complete by ogiekako2 on Saturday August 03, 2024 @01:01AM (#41144782)

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

[ Parent | on HN ]