4 ms·

TL;DR: all C implementations are FSMs (finite state machines, bounded by addressable memory based on wordsize) which are not Turing Complete because of the fini

TL;DR: all C implementations are FSMs (finite state machines, bounded by addressable memory based on wordsize) which are not Turing Complete because of the finite, as Turing machines have infinite tape.

wolf550e 2y ago
But you can use external storage for code and data, and that can be bigger than what can be addressed by the pointer size. The universe is finite, but most computations you would want to perform treat AWS S3 as infinite. Unless you want to brute force AES-128 or something.
- CobrastanJorji 2y ago
  S3 API isn't infinite. An object's name is limited to 1024 characters, and objects are limited to 5 TB. Buckets are limited to 63 characters. One could imagine a memory API with infinite storage, perhaps some sort of null-terminated addresses with no defined upper bound, but it'd be different than that.
  - tialaramex 2y ago
    None of which matters because: You'd need to store it, and our universe is finite, so there isn't enough room. Much worse the universe despite being finite is already so enormous and growing that you cannot cross it, so it would be impossible to actually perform computation as even if the data exists it can't necessarily ever be moved from where it is to the site of computation - it may get further away instead despite travelling as fast as possible.
- Rhapso 2y ago
  > but most computations Fit on a normal machine c99 runs on. The second you say "most computations" you stopped talking about Turing Completeness. Wait until you find out all memory lookups are O(n^0.5) too (assuming a holographic universe)
upon_drumhead 2y ago
Is this applicable to all actual programming languages or hardware? I struggle to think of a case where there isn't a bounded limit in practice.
- ForOldHack 2y ago
  If your design just calls for a pointer to memory, and your design leaves the size of a pointer, and the size of memory to the implementer, then both the size of memory, and the size of a pointer can grow without bound, like a Turning machine tape. Again, if a input language is Turing complete, then the langugage is Turing complete.
- olliej 2y ago
  The definition being used is pretty much useless, it’s literally “c cannot have infinite state”, which applies to literally anything that actually exists.
Am4TIfIsER0ppos 2y ago
Oh so nothing is turing complete because all computers and even the universe is finite?
- burkaman 2y ago
  No actual implementation of a language is Turing complete because the universe is finite, but a language specification could be. I think the argument here is that even if you had a computer with infinite memory, if you implemented C99 per the specification it would not be Turing complete.
  - olliej 2y ago
    The literal definition of Turing completeness means that if you can use an environment to implement a Turing machine, the environment is necessarily Turing complete.
    - cowboylowrez 2y ago
      yeah, couldn't the "tape" just be the hard drive accessed with the 64 bit file operations?
tialaramex 2y ago
If that's all the post says thanks for saving me the reading. A useful perspective to contrast to this idea that it's not a "real" Turing machine if you don't have infinite tape (and thus, no such machines can ever exist) is the Busy Beaver (perpetual favourite of Hacker News, just use the search at the bottom to find such topics). Some very small beavers are already completely beyond our ability to reason about because they express unsolved problems of mathematics.
- fsckboy 2y ago
  my tl;dr was about what the post hinges on. There are some theoretic-interesting comments (such as the following, below), but overall the discussion on the page is like smart first year CS students' classroom debate when they learn about Turing machines. Nothing wrong with it, useful to refresh, but no new ground. the aforementioned comment from TFA: C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, va_args can be used to implement a pointerless pointer. Of course, a real implementation of the variadic argument API is probably going to have a pointer somewhere, but in our abstract machine it can be implemented using magic instead.
  - jcranmer 2y ago
    va_list isn't quite enough to get you theoretically infinitely-addressable memory. A va_list is a blittable struct [1], and thus has a size, which means you can only have a finite number of them in your program. And the only way to push onto a va_list is to create a new one (by variadic function call), which also implies a maximum bound on the size of a va_list even with pointerless pointers. [1] Whether that copy is meaningfully usable is a different matter, which is why va_copy exists.
jvanderbot 2y ago
How is it that any computational device in physical reality is turing complete, since it must fit in our universe which can hold finite information? Doesn't that basically render the practical definition useless?
- olliej 2y ago
  I think the post is just a pedant/gotcha argument that is correct only in the “technically correct” sense, but is otherwise useless, as the same argument applies to literally any “Turing complete” system.
  - mort96 2y ago
    > the same argument applies to literally any “Turing complete” system. Only physical "Turing complete" systems. JavaScript, as specified by ECMA, is properly Turing machine; you can express a program which will allocate an arbitrary amount of objects. In the "JavaScript abstract machine", there is no upper limit. In C, there is necessarily a finite upper limit to the amount of objects allocated, since every object needs a unique address and addresses are represented by finite-bit pointers. That means that the "C abstract machine" as defined by ISO can not even in principle allocate arbitrarily many objects. (And yes, this all means that any Turing-machine-like systems built in the real world aren't proper Turing machines, since strictly speaking, a Turing machine is a theoretically construct with an infinitely long tape.)
- mort96 2y ago
  Their tl;dr isn't quite right. Any physical computing system has finite capacity, so you're right, no physical computing system is actually Turing complete. However, in most languages (JavaScript, Python, Java, ...) there's no concept of an object's location in memory as expressed by a finite number of bits. In those languages, you can express programs which will create an ever increasing number of objects. Trying to run that program will eventually cause a crash as you run out of space, but the source code itself encodes a program which would allocate objects with no upper bound. That's not the case for C. In C, every object has a unique address. That address is encoded in a fixed number of bits. As such, you can't even write source code which allocates objects with no upper bound; the upper bound will always be 2 to the power of the number of bits in a pointer.
ForOldHack 2y ago
TS;SI: Unless you have a receipt for "A new kind of science" AND "Gödel, Escher, Bach" You can forget figuring out if you know what you are saying: Rule 110 is Turing complete. Mathematica, for which the proof of Rule 110 is Turing Complete. C++ The programming language, for which Mathemetica is written in, is Turing Complete. All the theory is correct, BUT any implementation of Rule 110, Mathemetica and C++ are NOT Turing Complete, even if you turned every atom in the universe into the tape of a Turing machine, because the universe is finite. It has a finite number of atoms, but the theory? You have made an arbitrary causal network between the idea of Rule 110, and its implementation in C++. Its arbitrary, and minds much greater than yours can enjoy and understand this distinction, as does Stephen, and I. See Pages 770ff. You can compile rule 110 into a Mathemetica notebook, you can output it in x86 assembler. Since they are the same, i.e. they produce the exact outputs, and can determine computability "Turing completeness is a term in computer science that describes the ability of a system to compute any possible calculation or program, and can be used to describe modern programming languages (Python, C++, etc.). Turing complete describes a programmable system that can solve any computational problem." Now, how about a little bit of reading? https://philarchive.org/archive/CASOTC-3 https://philarchive.org/archive/CASOTC-3 "Virtually all programming languages today are Turing-complete." https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness
- djtriptych 2y ago
  Not sure it's true that there are a finite number of "atoms" or particles with quantum fluctuations + uncertainty around singularities but would love a smart person to chime in on that.
  - jvanderbot 2y ago
    A better way of saying it is that the universe has a limited amount of information it can contain.
  - shagie 2y ago
    PBS Space Time - How Much Information is in the Universe? https://youtu.be/XxVlGAFX7vA https://youtu.be/XxVlGAFX7vA It is a finite number and it's a big number, but still finite (and proven). https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound Also the playlist Understanding the Holographic Universe from PBS Space Time https://www.youtube.com/watch?v=qPKj0YnKANw&list=PLsPUh22kYmNCHVpiXDJyAcRJ8gluQtOJR https://www.youtube.com/watch?v=qPKj0YnKANw&list=PLsPUh22kYm... and Entropy Explained! https://www.youtube.com/watch?v=nhy4Z_32kQo&list=PLsPUh22kYmNCzNFNDwxIug8q1Zz0Mj60H https://www.youtube.com/watch?v=nhy4Z_32kQo&list=PLsPUh22kYm...
olliej 2y ago
Yeah the whole post is stupid, but it’s also just wrong: c is not bound by pointer size. A Turing machine that you implement in C as “the tape is a single array in address space” would be, but that’s not what is required for Turing completeness. The entire argument about pointer size is facetious - programs have operated over data that is larger than address space for ever, and is not hard to manage. But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be. If the real argument is “to be turing complete means that a Turing machine must be able to have infinite state”, then the argument is only technically true, but that’s argument applies equally to every Turing complete system.
- colevee 2y ago
  > Yeah the whole post is stupid, but it’s also just wrong: c is not bound by pointer size. > But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be. It isn't stupid. The post is not about "real world" implementations. The question was about C99's abstract semantics. As the first answer points out: > (Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)
  - olliej 2y ago
    In the C abstract machine there is no restriction on the stack size, and the nature of the stack (or that pointers are involved in it) is opaque, so within the definition of the language the call stack is infinitely sized. So if we want to be pedants about what is or is not "in the language" (though I'll note that IO routines are in the language), there is our infinite storage that does not depend on limits to pointer size.
Brych 2y ago
That's not a good summary - later in the answer author shows a way to go beyond FSMs, up to deterministic pushdown automata. They sidestep the issue of addressable memory by using the call stack and unaddressable `register` variables. C implementations are allowed to have no limit on recursion depth and have unlimited `register` variables, allowing us to pass data between caller and callee without using addressable memory, which gives us the power of DPA, but not much more.
- deleted 2y ago
  [deleted]

wolf550e 2y ago

But you can use external storage for code and data, and that can be bigger than what can be addressed by the pointer size. The universe is finite, but most computations you would want to perform treat AWS S3 as infinite. Unless you want to brute force AES-128 or something.

CobrastanJorji 2y ago
S3 API isn't infinite. An object's name is limited to 1024 characters, and objects are limited to 5 TB. Buckets are limited to 63 characters. One could imagine a memory API with infinite storage, perhaps some sort of null-terminated addresses with no defined upper bound, but it'd be different than that.
- tialaramex 2y ago
  None of which matters because: You'd need to store it, and our universe is finite, so there isn't enough room. Much worse the universe despite being finite is already so enormous and growing that you cannot cross it, so it would be impossible to actually perform computation as even if the data exists it can't necessarily ever be moved from where it is to the site of computation - it may get further away instead despite travelling as fast as possible.
Rhapso 2y ago
> but most computations Fit on a normal machine c99 runs on. The second you say "most computations" you stopped talking about Turing Completeness. Wait until you find out all memory lookups are O(n^0.5) too (assuming a holographic universe)

upon_drumhead 2y ago

Is this applicable to all actual programming languages or hardware? I struggle to think of a case where there isn't a bounded limit in practice.

ForOldHack 2y ago
If your design just calls for a pointer to memory, and your design leaves the size of a pointer, and the size of memory to the implementer, then both the size of memory, and the size of a pointer can grow without bound, like a Turning machine tape. Again, if a input language is Turing complete, then the langugage is Turing complete.
olliej 2y ago
The definition being used is pretty much useless, it’s literally “c cannot have infinite state”, which applies to literally anything that actually exists.

Am4TIfIsER0ppos 2y ago

Oh so nothing is turing complete because all computers and even the universe is finite?

burkaman 2y ago
No actual implementation of a language is Turing complete because the universe is finite, but a language specification could be. I think the argument here is that even if you had a computer with infinite memory, if you implemented C99 per the specification it would not be Turing complete.
- olliej 2y ago
  The literal definition of Turing completeness means that if you can use an environment to implement a Turing machine, the environment is necessarily Turing complete.
  - cowboylowrez 2y ago
    yeah, couldn't the "tape" just be the hard drive accessed with the 64 bit file operations?

tialaramex 2y ago

If that's all the post says thanks for saving me the reading. A useful perspective to contrast to this idea that it's not a "real" Turing machine if you don't have infinite tape (and thus, no such machines can ever exist) is the Busy Beaver (perpetual favourite of Hacker News, just use the search at the bottom to find such topics). Some very small beavers are already completely beyond our ability to reason about because they express unsolved problems of mathematics.

fsckboy 2y ago
my tl;dr was about what the post hinges on. There are some theoretic-interesting comments (such as the following, below), but overall the discussion on the page is like smart first year CS students' classroom debate when they learn about Turing machines. Nothing wrong with it, useful to refresh, but no new ground. the aforementioned comment from TFA: C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, va_args can be used to implement a pointerless pointer. Of course, a real implementation of the variadic argument API is probably going to have a pointer somewhere, but in our abstract machine it can be implemented using magic instead.
- jcranmer 2y ago
  va_list isn't quite enough to get you theoretically infinitely-addressable memory. A va_list is a blittable struct [1], and thus has a size, which means you can only have a finite number of them in your program. And the only way to push onto a va_list is to create a new one (by variadic function call), which also implies a maximum bound on the size of a va_list even with pointerless pointers. [1] Whether that copy is meaningfully usable is a different matter, which is why va_copy exists.

jvanderbot 2y ago

How is it that any computational device in physical reality is turing complete, since it must fit in our universe which can hold finite information? Doesn't that basically render the practical definition useless?

olliej 2y ago
I think the post is just a pedant/gotcha argument that is correct only in the “technically correct” sense, but is otherwise useless, as the same argument applies to literally any “Turing complete” system.
- mort96 2y ago
  > the same argument applies to literally any “Turing complete” system. Only physical "Turing complete" systems. JavaScript, as specified by ECMA, is properly Turing machine; you can express a program which will allocate an arbitrary amount of objects. In the "JavaScript abstract machine", there is no upper limit. In C, there is necessarily a finite upper limit to the amount of objects allocated, since every object needs a unique address and addresses are represented by finite-bit pointers. That means that the "C abstract machine" as defined by ISO can not even in principle allocate arbitrarily many objects. (And yes, this all means that any Turing-machine-like systems built in the real world aren't proper Turing machines, since strictly speaking, a Turing machine is a theoretically construct with an infinitely long tape.)
mort96 2y ago
Their tl;dr isn't quite right. Any physical computing system has finite capacity, so you're right, no physical computing system is actually Turing complete. However, in most languages (JavaScript, Python, Java, ...) there's no concept of an object's location in memory as expressed by a finite number of bits. In those languages, you can express programs which will create an ever increasing number of objects. Trying to run that program will eventually cause a crash as you run out of space, but the source code itself encodes a program which would allocate objects with no upper bound. That's not the case for C. In C, every object has a unique address. That address is encoded in a fixed number of bits. As such, you can't even write source code which allocates objects with no upper bound; the upper bound will always be 2 to the power of the number of bits in a pointer.

ForOldHack 2y ago

TS;SI: Unless you have a receipt for "A new kind of science" AND "Gödel, Escher, Bach" You can forget figuring out if you know what you are saying: Rule 110 is Turing complete. Mathematica, for which the proof of Rule 110 is Turing Complete. C++ The programming language, for which Mathemetica is written in, is Turing Complete. All the theory is correct, BUT any implementation of Rule 110, Mathemetica and C++ are NOT Turing Complete, even if you turned every atom in the universe into the tape of a Turing machine, because the universe is finite. It has a finite number of atoms, but the theory? You have made an arbitrary causal network between the idea of Rule 110, and its implementation in C++. Its arbitrary, and minds much greater than yours can enjoy and understand this distinction, as does Stephen, and I. See Pages 770ff. You can compile rule 110 into a Mathemetica notebook, you can output it in x86 assembler. Since they are the same, i.e. they produce the exact outputs, and can determine computability "Turing completeness is a term in computer science that describes the ability of a system to compute any possible calculation or program, and can be used to describe modern programming languages (Python, C++, etc.). Turing complete describes a programmable system that can solve any computational problem." Now, how about a little bit of reading? https://philarchive.org/archive/CASOTC-3 https://philarchive.org/archive/CASOTC-3 "Virtually all programming languages today are Turing-complete." https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness

djtriptych 2y ago
Not sure it's true that there are a finite number of "atoms" or particles with quantum fluctuations + uncertainty around singularities but would love a smart person to chime in on that.
- jvanderbot 2y ago
  A better way of saying it is that the universe has a limited amount of information it can contain.
- shagie 2y ago
  PBS Space Time - How Much Information is in the Universe? https://youtu.be/XxVlGAFX7vA https://youtu.be/XxVlGAFX7vA It is a finite number and it's a big number, but still finite (and proven). https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound Also the playlist Understanding the Holographic Universe from PBS Space Time https://www.youtube.com/watch?v=qPKj0YnKANw&list=PLsPUh22kYmNCHVpiXDJyAcRJ8gluQtOJR https://www.youtube.com/watch?v=qPKj0YnKANw&list=PLsPUh22kYm... and Entropy Explained! https://www.youtube.com/watch?v=nhy4Z_32kQo&list=PLsPUh22kYmNCzNFNDwxIug8q1Zz0Mj60H https://www.youtube.com/watch?v=nhy4Z_32kQo&list=PLsPUh22kYm...

olliej 2y ago

Yeah the whole post is stupid, but it’s also just wrong: c is not bound by pointer size. A Turing machine that you implement in C as “the tape is a single array in address space” would be, but that’s not what is required for Turing completeness. The entire argument about pointer size is facetious - programs have operated over data that is larger than address space for ever, and is not hard to manage. But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be. If the real argument is “to be turing complete means that a Turing machine must be able to have infinite state”, then the argument is only technically true, but that’s argument applies equally to every Turing complete system.

colevee 2y ago
> Yeah the whole post is stupid, but it’s also just wrong: c is not bound by pointer size. > But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be. It isn't stupid. The post is not about "real world" implementations. The question was about C99's abstract semantics. As the first answer points out: > (Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)
- olliej 2y ago
  In the C abstract machine there is no restriction on the stack size, and the nature of the stack (or that pointers are involved in it) is opaque, so within the definition of the language the call stack is infinitely sized. So if we want to be pedants about what is or is not "in the language" (though I'll note that IO routines are in the language), there is our infinite storage that does not depend on limits to pointer size.

Brych 2y ago

That's not a good summary - later in the answer author shows a way to go beyond FSMs, up to deterministic pushdown automata. They sidestep the issue of addressable memory by using the call stack and unaddressable `register` variables. C implementations are allowed to have no limit on recursion depth and have unlimited `register` variables, allowing us to pass data between caller and callee without using addressable memory, which gives us the power of DPA, but not much more.

deleted 2y ago
[deleted]