New answers tagged

1 vote

Help understand why FOL wff are enumerable, but FOL is undecidable

One line of reasoning here is that of Levin Search. https://people.idsia.ch/~juergen/optimalsearch.html The protocol is to try every program in order, and return the first one which “works.” If you ...
Bion Alex Howard's user avatar
0 votes

Help understand why FOL wff are enumerable, but FOL is undecidable

"Decidable" means "both semi-decidable and co-semi-decidable", so "Undecidable" just means "not both semi-decidable and co-semi-decidable". If a problem is semi-...
Natalie Clarius's user avatar

Top 50 recent answers are included