[sandywaffles]

Well considering I just saw a post recently saying `find` + `mkdir` is Turing Complete, I sure as hell hope C99 is as well.

[jvanderbot]

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]

Run 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.

[lcnPylGDnU4H9OF]

In 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://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

[tempodox]

Rule 110.

https://ogiekako.vercel.app/blog/find_mkdir_tc

[sakras]

Unfortunately not :)

On a given implementation of C, a pointer has some specific size (let's call it S). This means that we can address 2^S bytes of memory. Each byte has CHAR_BIT bits, so can be in 2^CHAR_BIT states, meaning we have 2^(S + CHAR_BIT) possible states memory can be in. Since there's a finite number of states, it's not a Turing machine.

[Scarblac]

Just implement find and mkdir and make the Turing machine using those.

[eMSF]

Why does everything have to fit in the memory all of a sudden? Open files, there's your infinite tape.