4 ms·

> * or simply impossible* how can anything be possible in one turing complete language but not at all possible in another?

by exit 15y ago

derleth 15y ago
> how can anything be possible in one turing complete language but not at all possible in another? Rephrase that as 'only possible if you write a Lisp implementation in that language' and you'll have the right idea.
danssig 15y ago
Of course it's possible. The question is; how much work is it going to be? Will I have to use my turing complete language to implement Lisp to do it? In that case I would accept "impossible" as shorthand.
- exit 15y ago
  sure, i would have understood "impossible" as shorthand if it hadn't immediately followed "quite difficult". "quite difficult or simply impossible to express" i thought i was about to learn something interesting about the reducibility of languages.
deleted 15y ago
[deleted]
swannodette 15y ago
Turing completeness says absolute nothing about performance. If my embedded logic programming library takes 2ms to run a query and yours takes an hour - I can actually put mine to useful work. Granted many languages simply move this kind of work to external C dependencies and such. However this doesn't address the other kinds of language extension such as idiomatic ad-hoc type systems and predicate dispatch I mentioned. Why shouldn't our programming languages capture these heterogenous use cases comfortably?
xyzzyz 15y ago
Ah, yet another misapplication of the "Turing completeness" idea. Turing completeness is about results, not methods of computation. If two languages are said to be Turing complete, it means that they are able to compute exactly the same set of functions, and not that they do it in exactly the same way. For instance, you have a problem that in one language is solvable in O(n), but in the other it provably requires Omega(n lg n), because certain constructs (e.g., random-access arrays) are missing from it.
yters 15y ago
Kolmogrov complexity proves that while language A can emulate capability X from language B, it is impossible to do so without writing B in A. In which case, it is still B doing X. So, in a literal sense, it can be impossible to do X in A and possible to do X in B, even though A and B are Turing complete.
- exit 15y ago
  thanks, this is the kind of answer i was hoping for

> * or simply impossible* how can anything be possible in one turing complete language but not at all possible in another?

by exit 15y ago

> * or simply impossible* how can anything be possible in one turing complete language but not at all possible in another?

derleth 15y ago

> how can anything be possible in one turing complete language but not at all possible in another? Rephrase that as 'only possible if you write a Lisp implementation in that language' and you'll have the right idea.

danssig 15y ago

Of course it's possible. The question is; how much work is it going to be? Will I have to use my turing complete language to implement Lisp to do it? In that case I would accept "impossible" as shorthand.

exit 15y ago
sure, i would have understood "impossible" as shorthand if it hadn't immediately followed "quite difficult". "quite difficult or simply impossible to express" i thought i was about to learn something interesting about the reducibility of languages.

deleted 15y ago

[deleted]

swannodette 15y ago

Turing completeness says absolute nothing about performance. If my embedded logic programming library takes 2ms to run a query and yours takes an hour - I can actually put mine to useful work. Granted many languages simply move this kind of work to external C dependencies and such. However this doesn't address the other kinds of language extension such as idiomatic ad-hoc type systems and predicate dispatch I mentioned. Why shouldn't our programming languages capture these heterogenous use cases comfortably?

xyzzyz 15y ago

Ah, yet another misapplication of the "Turing completeness" idea. Turing completeness is about results, not methods of computation. If two languages are said to be Turing complete, it means that they are able to compute exactly the same set of functions, and not that they do it in exactly the same way. For instance, you have a problem that in one language is solvable in O(n), but in the other it provably requires Omega(n lg n), because certain constructs (e.g., random-access arrays) are missing from it.

yters 15y ago

Kolmogrov complexity proves that while language A can emulate capability X from language B, it is impossible to do so without writing B in A. In which case, it is still B doing X. So, in a literal sense, it can be impossible to do X in A and possible to do X in B, even though A and B are Turing complete.

exit 15y ago
thanks, this is the kind of answer i was hoping for