3 ms·
> first order logic is so powerful that it lets you describe everything you can in principle perform with a computer Not quite sure what you're referring to he
by ScottBurson 9y ago
> first order logic is so powerful that it lets you describe everything you can in principle perform with a computer
Not quite sure what you're referring to here, but induction schemata seem to be a notable exception. There's a reason higher-order logic is often preferred for software verification.
I guess FOL is adequate if you're allowed to have an infinite number of axioms, but that doesn't seem very satisfying (pun intended).
- zmonx 9y agoI am referring here to the fact that first-order logic is sufficiently expressive to describe how a Turing machine works, making FOL Turing-complete and thus, as a special case, making every computation you can carry out on a computer expressible in FOL, as a first-order formula that is satisfiable iff the TM accepts the input.