3 ms·

agreed. For example C is considered general purpose despite not being Turing complete.

by eadler 4y ago

bmitc 4y ago
Is it really not? Do you have a reference for that? I can’t find anything that says C isn’t Turing complete.
- ogogmad 4y ago
  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.
  - avmich 4y ago
    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.
- Jorengarenar 4y ago
  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.
ausudhz 4y ago
I think C is Turing complete for sure.
naasking 4y ago
> For example C is considered general purpose despite not being Turing complete. Actually, C fails the general purpose language criterion too, because it's simply not a good choice for many different and common uses. It's a good choice for very specific uses at this point.
cultofmetatron 4y ago
c is only technically not Turing complete because it runs on real machine with finite memory. by that definition, no programming language is turing complete.

agreed. For example C is considered general purpose despite not being Turing complete.

by eadler 4y ago

agreed. For example C is considered general purpose despite not being Turing complete.

bmitc 4y ago

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

ogogmad 4y ago
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.
- avmich 4y ago
  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.
Jorengarenar 4y ago
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.

ausudhz 4y ago

I think C is Turing complete for sure.

naasking 4y ago

> For example C is considered general purpose despite not being Turing complete. Actually, C fails the general purpose language criterion too, because it's simply not a good choice for many different and common uses. It's a good choice for very specific uses at this point.

cultofmetatron 4y ago

c is only technically not Turing complete because it runs on real machine with finite memory. by that definition, no programming language is turing complete.