Pierwsze poważne próby rozwiązania dziesiątego problemu Hilberta zostały poczynione przez Martina Davisa w 1950 roku. Próbowano wykazać, że dla każdego rekurencyjnie przeliczalnego zbioru istnieje odpowiadający mu wielomian z całkowitymi współczynnikami, taki że równanie diofantyczne ma rozwiązanie wtw., gdy należy do (a więc mówiąc krócej, że każdy rekurencyjnie przeliczalny zbiór jest zbiorem diofantycznym). Możemy zauważyć, że istnienie algorytmicznej procedury determinującej postać wielomianu dla określonego zbioru jest sprzeczne z pozytywnym rozstrzygnięciem problemu Hilberta. Załóżmy, że algorytm istnieje i niech będzie rekurencyjnie przeliczalnym zbiorem liczb całkowitych, który nie jest zbiorem rekurencyjnym. Wtedy (wbrew nierekurencyjności zbioru ) można by w skończonej liczbie kroków ustalić przynależność dowolnej liczby całkowitej do zbioru najpierw stosując algorytm w celu ustalenia postaci a następnie pytając algorytm Hilberta, czy ma rozwiązanie. Zatem istnienie algorytmu Hilberta determinującego rozwiązywalność wszystkich równań diofantycznych sprowadzałoby się do sprzeczności.