Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Is it really not? Do you have a reference for that? I can’t find anything that says C isn’t Turing complete.


It's a troll. But not wrong.

C treats computer memory as an array of bytes indexed by a pointer type that can take only finitely many values. If the pointer type can be cast losslessly to `long int` - which is usually understood to be 64 bit - then this byte array has precisely 2^64 entries. That implies that C programs have an absolute limit on the amount of memory they can use (2^64 bytes). That's obviously true, because each call to `malloc` fills up another entry of this finite byte array. C therefore can't simulate a Turing Machine, because a Turing Machine can use an unbounded amount of memory.

If you use a file system, or another source of external memory or storage, then the above argument no longer applies.


A long time ago computers with limited RAM address space - and problems which didn't fit - used various tricks to deal with that. Overlays, paged memory, virtual memory - all that could effectively address more memory than address space allows.

So I'd argue C-as-specification (not as existing implementation, I don't know) is _theoretically_ Turing complete. Yes I agree it's a troll.


In strict sense of being Turing-Complete, noting is TC, because of physical world limitations (infinity doesn't really exists).

If we use "useful" definition of being Turing-Complete, then even `printf()` alone is already TC.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: