3 ms·

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 arra

by 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.
  - colevee 2y ago
    [dead]

by olliej 2y ago

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.
- colevee 2y ago
  [dead]