Dugaan Hartmanis-Stearns dan bilangan transendental yang dapat dihitung

Pada 1965 artikel " Pada kompleksitas komputasi algoritma " oleh Hartmanis dan Stearns, penulis menduga bahwa jika real-time Turing Machine menghitung jumlah riil , misalnya, basis 10, maka adalah salah bilangan rasional atau nomor transendental. $r$ $r$

Apakah ada bilangan transendental yang dapat dihitung yang tidak dapat dihitung oleh mesin Turing real-time di, misalnya, basis 10?

cc.complexity-theory reference-request examples XL _At_Here_There
sumber

Jika saya memahami pertanyaan Anda dengan benar, konstanta Chaitin adalah contoh angka-angka seperti itu: Mereka adalah transendental dan tidak dapat dihitung sama sekali.

Bruno

@ Bruno, tetapi konstanta Chaitin tidak dapat dihitung, atau semicomputable, jadi bukan angka yang merupakan angka transendental yang dapat dihitung dan tidak dapat dihitung oleh mesin Turing real-time.

XL _At_Here_There

Kesalahan saya, saya tidak memperhatikan bahwa Anda meminta nomor yang dapat dihitung ...

Bruno

Jawaban:

Biarkan menjadi bahasa lengkap-EXPTIME, dan biarkan menjadi real yang sesuai. Jelas dapat dihitung. Angka tidak boleh aljabar karena bit ke- dari angka aljabar dapat dihitung dalam waktu ( Datta dan Pratap ). Karena th bit dari sejumlah dihitung oleh mesin Turing real-time dapat dihitung dalam waktu , tidak dapat dihitung dengan real-time mesin Turing. $L$ $r \in (0,1)$ $r$ $r$ $n$ $n^{O(1)}$ $n$ $O(n)$ $r$

Yuval Filmus
sumber

Luar biasa, Tapi saya harus memikirkannya dengan cermat. Dan saya baru saja menemukan bahwa Datta dan Pratap adalah sebuah makalah yang baru saja diterbitkan.

XL _At_Here_There

Agaknya telah diketahui bahwa ekspansi biner dari angka-angka aljabar dapat dihitung dalam waktu polinomial. Kertas mereka hanya yang pertama yang bisa saya temukan, dan itu benar-benar membuktikan hasil yang lebih kuat.

Yuval Filmus

Ya, saya telah lama menduga bahwa ekspansi biner dari angka-angka aljabar dapat dihitung dalam waktu polinomial, tetapi belum menemukan bukti tentang itu, terima kasih lagi atas jawaban Anda dan makalah yang direferensikan

XL _At_Here_There