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