Questions tagged [computability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8 votes
1 answer
531 views

Why do most programming languages derive min/max from comparison operators, rather than the other way round?

For example, recall the Ord class of Haskell: ...
Dannyu NDos's user avatar
13 votes
2 answers
463 views

Can Felleisen's expressivity metric be abused to construct ever more expressive languages that aren't actually more expressive?

The idea of comparing the expressivity of languages objectively using various metrics is very interesting. A particularly interesting answer is Matthias Felleisen's formal notion of expressivity. I ...
Bruce Adams's user avatar
  • 2,833
14 votes
2 answers
1k views

How to prevent undecidable type systems?

Some languages have type systems complex enough to embed undecidable problems in the type system. This famous post details implementing a Turing-complete language in Rust's type system, and Swift's ...
Bbrk24's user avatar
  • 8,907
20 votes
4 answers
671 views

How can I check if a new language is Turing-complete?

What would be the easiest way to show if a newly designed language is Turing complete or not? Simulating a Turing machine could be cumbersome; can it be inferred from certain characteristics? For ...
Glorfindel's user avatar
  • 1,483