Varian dari fungsi berang-berang yang sibuk

Membaca pertanyaan ini, " Masalah RE yang tidak dapat dipastikan tetapi tidak menyelesaikan Turing ", bahasa berikut muncul di benak saya:

Jika adalah fungsi berang-berang yang sibuk (skor maksimum yang dapat dicapai di antara semua penghentian 2-simbol n-state mesin Turing dari tipe yang dijelaskan di atas, ketika dimulai pada pita kosong), tentukan fungsinya: $\Sigma(\cdot)$

B B (⟨ M ⟩) = {\begin{cases} 1 & ⟨ M ⟩ computes Σ (\cdot) \\ 0 & otherwise \end{cases}

$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$

Sekarang tentukan bahasanya:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

Apakah $L$ secara berulang dihitung? (itu harus kembali: hanya mensimulasikan dalam M paralel dengan semua TM dengan panjang yang sama, dan jika $M$ berhenti dan lain $M'$ berhenti dengan skor yang lebih tinggi tambahkan M ke enumerasi).

Bisakah kita mengurangi masalah penghentian menjadi $L$ ? (tampaknya itu tidak bisa "menangkap" penghentian berang-berang yang sibuk)

computability turing-machines Vor
sumber

Apakahjumlah negara bagian?

| ⟨ M ⟩ |

$|\langle M \rangle|$

Pål GD

Kapan Anda akan menghitung yang tidak berhenti ke ? tidak bisa menjadi RE kecuali jika Anda menghitung semua anggotanya, dan prosedur yang Anda jelaskan hanya menyebutkan yang benar-benar berhenti.

M

$M$

L

$L$

L

$L$

Steven Stadnicki

@ PålGD: ya itu adalah jumlah negara bagian (negara yang berhenti dikecualikan)

Vor

@StevenStadnicki: Secara implisit saya berasumsi bahwa hanya berisi mesin yang berhenti ... mungkin saya harus mengklarifikasi dalam pertanyaan (biarkan saya berpikir sedikit, mungkin membuat pertanyaan itu sepele).

L

$L$

Vor

@ Kaveh Ini bahkan bukan masalah janji - Anda bisa mendefinisikan (seperti yang saya yakini sebagai tujuan OP) sebagai .

L

$L$

L = {⟨ M ⟩ | M halts \land B B (⟨ M ⟩) = 0}

$L=\{\langle M\rangle | M\ \text{halts} \wedge BB(\langle M\rangle) = 0\}$

Steven Stadnicki

Jawaban:

Saya tidak percaya saya tidak melihat ini sebelumnya - tapi ya, dengan oracle untuk Anda dapat memecahkan masalah yang tersendat-sendat. Jelas sebuah oracle untuk memberi kita 'secara rekursif' semua mesin penghenti Beaver yang tidak sibuk, jadi pertanyaannya adalah 'bisakah kita mencari tahu secara rekursif dalam apa berang-berang yang sibuk itu?'. Tentukan sebagai fungsi hitungan 'berang tersibuk kedua'; yaitu, skor tertinggi kedua yang dapat dicapai di antara semua penghentian TM dua simbol . Kuncinya di sini adalah bahwa ada fungsi rekursif sehingga (hampir pasti bahwa $L$ $L$ $L$ $\Sigma_2(n)$ $n$ $f()$ $\Sigma(n)\leq\Sigma_2(f(n))$ $f(n)=n+1$ akan melakukan trik, pada kenyataannya, tetapi itu membutuhkan mengetahui bahwa fungsi BB benar-benar meningkat): diberi mesin ukuran yang mencetak 1 pada kasetnya dan kemudian berhenti, ada beberapa dan dua mesin masing-masing berukuran yang mencetak tepat 1s dan persis 1s, masing-masing, pada kaset mereka - dan ini berlaku untuk mesin 'sibuk berang-berang' meskipun kami tidak tahu secara eksplisit . Ini berarti bahwa memiliki fungsi terikat pada 'berang-berang sibuk kedua' untuk memberikan batas untuk fungsi berang-berang sibuk pada $M$ $n$ $\Sigma(M)$ $c\gt 1$ $\leq cn$ $\Sigma(M)$ $\Sigma(M)+1$ $M$ $M$ $f(n)$ $n$ ; tetapi kemudian memiliki ini, mudah untuk memecahkan masalah penghentian untuk TM ukuran - jika maka katakan bahwa berhenti; jika tidak, cari mesin yang paling lama beroperasi ukuran di (yang dapat dilakukan secara rekursif karena hanya ada banyak mesin ukuran ) dan mensimulasikan untuk langkah-langkah yang dibutuhkan mesin untuk berhenti. Jika tidak berhenti dalam waktu itu maka tidak mungkin berhenti. $M$ $n$ $\langle M\rangle\in L$ $M$ $f(n)$ $L$ $\leq f(n)$ $M$ $M$ $M$

Steven Stadnicki
sumber

Terima kasih; terinspirasi oleh jawaban Anda, saya menemukan cepat (sepele) -: pengurangan langsung dari masalah berhenti dalam jawaban yang terpisah.

Vor

Ini adalah versi ulang dari jawaban Steven yang baik, dengan pengurangan eksplisit dari masalah Berhenti.

Diberikan build yang menjalankan on dan jika berhenti di sebelah kanan rekaman, tulis 0 dan berhenti. $\langle M \rangle, w$ $M'$ $M$ $w$

Jika berhenti, karena ada TM setara dengan ukuran yang sama yang menulis 1 dan berhenti; sehingga kita dapat menggunakan penentuan untuk untuk memeriksa apakah perhentian di ( perhentian di IFF ) $M'$ $BB(M')=0$ $L$ $M$ $w$ $M$ $w$ $M' \in L$

... ternyata pertanyaannya memang sepele :-)

Vor
sumber