13 ms·
Well considering I just saw a post recently saying `find` + `mkdir` is Turing Complete, I sure as hell hope C99 is as well.
by sandywaffles 2y ago
Well considering I just saw a post recently saying `find` + `mkdir` is Turing Complete, I sure as hell hope C99 is as well.
- jvanderbot 2y agoI'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
- sakras 2y agoUnfortunately 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 2y agoJust implement find and mkdir and make the Turing machine using those.
- eMSF 2y agoWhy does everything have to fit in the memory all of a sudden? Open files, there's your infinite tape.
- jcranmer 2y agoYour position in a file has to be uniquely specifiable with fpos_t, so you can't have an infinite file in C. > fpos_t is a complete object type other than an array type capable of recording all the information needed to specify uniquely every position within a file. [7.23.1p3 of N3054 working draft of C2x, as that's what I have open right now.]