de berekenbaarheid zelfst.naamw. (v.) het berekend kunnen worden 
1) Rationaliteit 
Een herkenner voor een probleem 'P' is een turingmachine die alle ja-instanties van het probleem herkent, maar niet noodzakelijk alle nee-instanties van het probleem afwijst. Gegeven een ja-instantie van 'P' zal de herkenner altijd in de accepterende toestand eindigen, maar gegeven een nee-instantie mag de machine ofwel in de afwijzende toestand ei...