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... Gevonden op https://nl.wikipedia.org/wiki/Berekenbaarheid