Hipoteza Hartmanisa-Stearnsa i obliczalne liczby transcendentalne

W artykule z 1965 r. „ O złożoności algorytmów ” autorstwa Hartmanisa i Stearnsa autorzy przypuszczają, że jeśli maszyna Turinga w czasie rzeczywistym oblicza liczbę rzeczywistą na przykład w podstawie 10, to jest albo liczbą wymierną, albo liczbą liczba transcendentalna. $r$ $r$

Czy istnieje obliczalna liczba transcendentalna, która nie jest obliczalna przez maszynę Turinga w czasie rzeczywistym, na przykład w bazie 10?

cc.complexity-theory reference-request examples XL _At_Here_There
źródło

Jeśli dobrze rozumiem twoje pytanie, stałe Chaitin są przykładami takich liczb: są transcendentalne i w ogóle nie są obliczalne.

Bruno

@ Bruno, ale stałe Chaitina nie są obliczalne ani półkomputerowe, więc to nie liczby są obliczalną liczbą transcendentalną i nie są obliczalne przez maszynę Turinga w czasie rzeczywistym.

XL _At_Here_There

Mój błąd, nie zauważyłem, że poprosiłeś o obliczalny numer ...

Bruno,

Odpowiedzi:

$L$ $r \in (0,1)$ $r$ $r$ $n$ $n^{O(1)}$ $n$ $O(n)$ $r$

Yuval Filmus
źródło

Doskonale, ale muszę się nad tym zastanowić. I właśnie odkryłem, że Datta i Pratap to artykuł, który został niedawno opublikowany.

XL _At_Here_There

Przypuszczalnie wiadomo było, że binarne rozszerzenie liczb algebraicznych można obliczyć w czasie wielomianowym. Ich artykuł jest tylko pierwszym, jaki udało mi się znaleźć, i faktycznie dowodzi lepszych rezultatów.

Yuval Filmus

Tak, od dawna przypuszczałem, że binarne rozszerzenie liczb algebraicznych można obliczyć w czasie wielomianowym, ale nie znalazłem na to żadnego dowodu, jeszcze raz dziękuję za odpowiedź i

odnośny