b'\n_START_ARTICLE_\nZbi\xc3\xb3r diofantyczny\n_START_SECTION_\nTwierdzenia Matiyasevicha\n_START_PARAGRAPH_\nTwierdzenie Matiyasevicha m\xc3\xb3wi, \xc5\xbce ka\xc5\xbcdy rekurencyjnie przeliczalny zbi\xc3\xb3r jest zbiorem diofantycznym. Zbi\xc3\xb3r  jest rekurencyjnie przeliczalny wtw. gdy istnieje taka maszyna Turinga , \xc5\xbce je\xc5\xbceli maszyna  dzia\xc5\x82aj\xc4\x85c na liczb\xc4\x99  ko\xc5\x84czy prac\xc4\x99 to . W spos\xc3\xb3b r\xc3\xb3wnowa\xc5\xbcny mo\xc5\xbcna powiedzie\xc4\x87, \xc5\xbce zbi\xc3\xb3r jest rekurencyjnie przeliczalny je\xc5\xbceli istnieje algorytm wypisuj\xc4\x85cy list\xc4\x99 wszystkich element\xc3\xb3w tego zbioru._NEWLINE_Implikacja odwrotna r\xc3\xb3wnie\xc5\xbc jest spe\xc5\x82niona. Je\xc5\xbceli  jest diofantyczn\xc4\x85 reprezentacj\xc4\x85 pewnego zbioru diofantycznego  to zbi\xc3\xb3r  jest rekurencyjnie przeliczalny. Algorytm wypisuj\xc4\x85cy wszystkie elementy zbioru  mo\xc5\xbcemy uzyska\xc4\x87 sprawdzaj\xc4\x85c r\xc3\xb3wno\xc5\x9b\xc4\x87  dla wszystkich mo\xc5\xbcliwych uporz\xc4\x85dkowanych, n+1-elementowych krotek  (kt\xc3\xb3rych jest przeliczalnie wiele z uwagi na przeliczalno\xc5\x9b\xc4\x87 iloczyn\xc3\xb3w kartezja\xc5\x84skich zbior\xc3\xb3w przeliczalnych).'