Zwykłym sposobem udowodnienia nierozstrzygalności jest redukcja problemu RE-zupełnego, takiego jak problem zatrzymania, trafność w logice pierwszego rzędu, spełnienie równań diofantycznych itp.
Wiadomo, że istnieją rekurencyjnie wyliczalne, ale nierozstrzygalne problemy, które nie są uzupełniane ponownie, ale są to sztuczne konstrukcje (to znaczy zestawy, które zostały zdefiniowane tylko w celu pokazania tego wyniku „gęstości”).
Jak poradzić sobie z udowodnieniem nierozstrzygalności bez ograniczenia problemu RE-zupełnego? Przekątna?