4 ms·
...and pigs can fly, if you throw them fast enough. This is just an encoding of a Turing-complete language into another, I don't see what's been demonstrated h
by fab13n 14y ago
...and pigs can fly, if you throw them fast enough.
This is just an encoding of a Turing-complete language into another, I don't see what's been demonstrated here.
- fauigerzigerk 14y agoI'm not sure this is even Turing complete considering the limitation he mentions: >The main limitation is that you need to know the size of the return value.
- jvranish 14y agoIt'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.
- Evbn 14y agoThat is a purely theoretical concern, not a practical blocker against any program anyone would ever run.
- fauigerzigerk 14y agoA program that determines the number of items it needs to store in a list only at runtime doesn't seem that theoretical to me.
- rauljara 14y agoAll programming languages and all programming styles can be similarly dismissed as encoding one Turing-complete form into another. Why pay attention to any of them? This article is clearly someone having fun with their language. It isn't a serious claim about C being functional, something which the author states explicitly if you read to the end.
- meaty 14y agoAnd if it was LISP doing this, people would be gushing all over it...
- andrewcooke 14y agohttp://news.ycombinator.com/item?id=4693920 http://news.ycombinator.com/item?id=4693920 "everything is turing complete" is a perfect example of the kind of middle-brow dismissal i understood pg to be talking about.