Laat zien dat W niet beslisbaar is.

Stel dat W beslisbaar is, dan moet er dus een TM zijn die W beslist.

W = {M | M is een deterministische TM die de functie f berekent}

f is berekenbaar (gegeven) dus er is een TM die deze functie berekent, noem deze TM A. Merk op dat elke M in W dezelfde taal heeft (nl. de functie f).

W heeft dus minimaal A

Stel nu een willekeurige andere TM M die ook f berekent, deze hoort dus ook in W

Reduceer EQtm <= W

de beslisser van W kan er als volgt uit zien

BW = "Op invoer M:
	1. Vergelijk L(A) met L(M), en accepteer als beide talen gelijk zijn, anders verwerpen"

Merk op dat stap 1 een mogelijkheid vereist om de talen van 2 TMs met elkaar te vergelijken. Dit kun je dus vervangen door een beslisser van EQtm.

EQtm is niet beslisbaar (zie boek voor het bewijs etc etc)

Dus W is dus ook niet beslisbaar