News for hackers. Stuff that matters.

A comment on `find` + `mkdir` is Turing complete. Parent comment

Re:`find` + `mkdir` is Turing complete by tomsmeding on Wednesday July 31, 2024 @04:42AM (#41117401)
On the other hand, a C running on a machine with a significantly larger address space would have appropriately larger pointers. The C standard does not specify any particular pointer bitwidth. With these things together, C as a language has a decent claim to Turing-completeness.
[ Parent | on HN ]
Re:`find` + `mkdir` is Turing complete by camel-cdr on Wednesday July 31, 2024 @04:46AM (#41117416)
Yes, but you still configure (choose a compiler) it to a fixed size before running, that is in my mind no different than specifying a fixed tape size, like in the find + mkdir example.
[ Parent | on HN ]
Re:`find` + `mkdir` is Turing complete by oecumena on Wednesday July 31, 2024 @09:35AM (#41119036)
For any C program there is a number N, that depends on the program, compiler, architecture, etc., but does not depend on the program input, such that the program won't be able to access more than N bits of state at any moment in any of its possible executions. Hence, the program is equivalent to a finite state automaton.
[ Parent | on HN ]