5 ms·
It's still Turing complete (though that's not saying much really). You can always grow the stack more :P
by jvranish 14y ago
It's still Turing complete (though that's not saying much really). You can always grow the stack more :P
- fauigerzigerk 14y agoI don't think that solves the problem. Whatever fixed stack size you choose, you still cannot write a program that determines the size of the lists at runtime. A Turing complete system would have to be able to do that. The only way I see is to allocate (almost) the entire machine memory to the stack, create one giant array in that chunk of memory and then put all lists in that single array. That's tantamount to reimplementing malloc on the stack.
- charliesome 14y agoAny physical machine cannot be Turing complete because it has a finite amount of RAM.
- fauigerzigerk 14y agoSure, but we're talking about whether or not this particular style of C can be Turing complete and I'm not sure it is, even on a machine with an infinite amout of RAM.
- jsight 14y agoA machine with an infinite amount of RAM can have an infinite stack size.
- fauigerzigerk 14y agoC arrays that live on the stack have to be created with a constant size (at least before C99). It's a limitation of the language regardless of any machine or stack size.
- Johngibb 14y agoIf we're going to grant that a machine can have infinite ram, surely we can grant that a spec of C can have infinite stack allocated arrays... :)
- deleted 14y ago[deleted]
- sp332 14y agoThat's already been granted in this argument. The question now is, given an infinite stack, is this programming style Turing-complete?
- Evbn 14y agoAddress space is not limited by RAM. The only concern is fixed vs expandable width address.