Twierdzenia Matijasiewicza Twierdzenie Matijasiewicza mówi, że każdy rekurencyjnie przeliczalny zbiór jest zbiorem diofantycznym. Zbiór jest rekurencyjnie przeliczalny wtw. gdy istnieje taka maszyna Turinga że jeżeli maszyna działając na liczbę kończy pracę to W sposób równoważny można powiedzieć, że zbiór jest rekurencyjnie przeliczalny jeżeli istnieje algorytm wypisujący listę wszystkich elementów tego zbioru.
Implikacja odwrotna również jest spełniona. Jeżeli jest diofantyczną reprezentacją pewnego zbioru diofantycznego to zbiór jest rekurencyjnie przeliczalny. Algorytm wypisujący wszystkie elementy zbioru możemy uzyskać sprawdzając równość dla wszystkich możliwych uporządkowanych, n+1-elementowych krotek (których jest przeliczalnie wiele z uwagi na przeliczalność iloczynów kartezjańskich zbiorów przeliczalnych).
Zobacz też dziesiąty problem Hilberta równanie diofantyczne
Bibliografia
Kategoria:Teoria liczb