Gap antara

$HT(n)$ $n$ $BB(n) = \max HT(n)$

Apa yang bisa kita katakan tentang angka terbesar kedua di ? Sebut ini . $HT(n)$ $BB_2(n)$

$BB_2(n)$ sepele tidak dapat dihitung, karena memungkinkan satu menghitung : tunggu satu mesin lagi untuk berhenti. Secara naif, saya berharap celah menjadi "sibuk berang-berang", tumbuh lebih cepat daripada fungsi yang dapat dihitung. Apakah ini terbukti? $BB(n)$ $BB(n) - BB_2(n)$

computability Geoffrey Irving
sumber

Misalkan salah satu dari n status tidak dapat dijangkau.

mic

@mic: Saya pikir itu tidak relevan.

tampaknya sangat tidak mungkin.

B B (n - 1) = B B_{2} (n)

$BB(n-1) = BB_2(n)$

Geoffrey Irving

Ini akan tergantung pada encoding. Jika Anda membalik status accept / reject, jumlah status tetap sama dan begitu juga waktunya untuk berhenti, yang akan membuat

B B (n) = B B_{2} (n)

$BB(n)=BB_2(n)$

Lance Fortnow

H T (n)

$HT(n)$

Apakah mungkin untuk membuktikan bahwa celah tersebut pada akhirnya tidak 1?

Geoffrey Irving

Jumlah status hanyalah gagasan kerumitan dari deskripsi fungsi yang dapat dihitung dalam suatu model, Anda dapat memilih model perhitungan apa saja dan penyandiannya sebagai string biner dan kemudian mengambil panjangnya sebagai n dan menentukan BB (n) berdasarkan itu dan semua hasil menarik tentang BB (n) masih benar, ada yang membosankan khusus tentang model TM dan jumlah negara.
Tidak ada yang mencegah mereka memilih model TM yang dimodifikasi. Umumnya pertanyaan-pertanyaan yang tidak invarian di bawah perubahan representasi TM seperti itu bukan tentang komputabilitas atau TM tetapi tentang representasi tertentu (seperti BB (n) mod 2, dll.) Dan kecuali ada alasan khusus untuk menarik mereka tidak layak mengejar imho. Itu adalah teka-teki yang bagus tapi tidak banyak nilainya. l Perhatikan bahwa "BB (n) tidak dapat dihitung" tidak berubah di bawah perubahan representasi TM.
Jadi, apakah pertanyaan ini tidak berubah di bawah perubahan representasi fungsi yang dapat dihitung? Jawabannya saya pikir tidak.

saya. Pertimbangkan representasi di mana kita memiliki dua status khusus 0 dan 1 dan 0 baik awal dan hanya dapat transisi ke 1 atau 0 tidak dapat dijangkau dan 1 adalah awal. Dalam pengkodean ini perbedaannya adalah 1.

ii. Pertimbangkan representasi lain di mana kami memiliki UTM plus bagian yang menulis n bit pada tape sebelum beralih ke UTM. Jadi pertanyaannya menjadi maks f (x) - 2ndmax f (x) di mana maks lebih dari n bit string dan di mana f adalah fungsi yang dapat dihitung sewenang-wenang. Kita hanya perlu menemukan fungsi yang dapat dihitung di mana ini tidak dapat dihitung. Saya belum terlalu memikirkannya tetapi nyali saya mengatakan ada fungsi yang dapat dihitung.

Kaveh
sumber

Semua ini tidak relevan, karena saya memilih mesin Turing standar sebagai konsep perhitungan saya. Saya setuju bahwa ada beberapa definisi umum yang berbeda (satu atau dua pita sisi, apakah pita tersebut mulai nol atau simbol kosong khusus), tetapi tidak seperti UTM yang telah disematkan sebelumnya yang Anda sebutkan.

Geoffrey Irving

n

$n$

Biarkan saya katakan dengan cara yang berbeda: mengapa Anda tertarik dengan jawabannya? Ini adalah teka-teki bagus seperti banyak lainnya tentang BB untuk representasi TM tertentu tetapi mereka tidak mengungkapkan apa pun tentang komputabilitas dan komputasi. Memilih standar untuk representasi TM adalah tindakan sewenang-wenang, orang dapat memilih representasi pertama saya di atas dan jawaban atas pertanyaan Anda adalah 1. Hanya karena disebut standar tidak menjadikannya istimewa di antara representasi.

Kaveh

Ini tidak berbeda dengan menanyakan apakah beberapa persamaan Diophantienne E yang dipilih secara acak memiliki solusi integer. Ada banyak persamaan seperti itu, tanpa alasan mengapa orang tertarik pada E, itu bukan pertanyaan yang sangat menarik. Ketika orang mengajukan pertanyaan seperti "computability of BB (n) mod 2" mereka pikir mereka mengajukan pertanyaan mendalam tentang computability sedangkan pada kenyataannya itu lebih seperti meminta kelarutan dari beberapa persamaan Diophantienne yang dipilih secara sewenang-wenang, itu hanya beberapa dari mereka terlihat lebih baik untuk mata.

Kaveh

Saya tertarik karena saya percaya jawabannya adalah sama untuk semua pengkodean nondegerate: tidak dapat dibuktikan, tidak dapat dibuktikan bahwa tidak dapat dibuktikan, dll. Tapi saya tidak tahu bagaimana mengucapkannya, jadi saya memilih satu. Fakta bahwa itu sepele untuk pengkodean yang dipilih secara khusus mirip dengan masalah penghentian yang dapat dipecahkan untuk mesin penghenti-oleh-konstruksi.

Geoffrey Irving

Gap antara

Jawaban: