Hacker News new | ask | show | jobs
by YellPika 4022 days ago
> From a type-theoretic perspective, a language can be either logically consistent by means of strong normalization xor Turing-complete.

This is a common misconception. A counter-example: take System F, add an `IO` monad, and add a function `fix : forall a. (a -> a) -> IO a` for general recursion. Our language is now Turing-complete, but remains consistent since any falsehoods produced by `fix` can't escape the `IO` type, e.g. you can prove `fix id : IO _|_`, but not `_|_`.

1 comments

Fair enough, and that's been one of the approaches to paraconsistency and inconsistency in modal logic, too. Of course, from a theorem-proving perspective, it's utterly useless, as with a proof-checker, at some point I need to escape the monadic container and get back into `Prop`.