3 ms·
I'm fairly certain that find + mkdir is not turing complete, it can only execute Rule 110 for so long before running out of space. But the claim applied only to
by jvanderbot 2y ago
I'm fairly certain that find + mkdir is not turing complete, it can only execute Rule 110 for so long before running out of space. But the claim applied only to the length of directory names, which I suppose are unbounded in abstract.
The limit of "Must run infinitely" will basically wreck any computer that will fit in this universe, won't it?
EDIT: Thanks for correction to rule 110
- olliej 2y agoRun infinitely with infinite memory, so yes we the “is it Turing complete” argument is “no because finite {X}” then a Turing machine is not Turing complete because it’s impossible to actually make an infinite Turing machine.
- mort96 2y agoA Turing machine is a theoretical construct with an infinite tape.
- lcnPylGDnU4H9OF 2y agoIn their post is a disclaimer from the author that they made a mistake in their initial proof. https://ogiekako.vercel.app/blog/find_mkdir_tc https://ogiekako.vercel.app/blog/find_mkdir_tc https://news.ycombinator.com/item?id=41115941 https://news.ycombinator.com/item?id=41115941 They also updated their proof (not saying whether it's valid or not, just updated): https://news.ycombinator.com/item?id=41127041 https://news.ycombinator.com/item?id=41127041
- tempodox 2y agoRule 110. https://ogiekako.vercel.app/blog/find_mkdir_tc https://ogiekako.vercel.app/blog/find_mkdir_tc