Menghentikan masalah tanpa referensi sendiri

Dalam masalah penghentian, kami tertarik jika ada mesin Turing yang dapat mengetahui apakah mesin Turing diberikan berhenti atau tidak pada input yang diberikan . Biasanya, buktinya mulai dengan menganggap seperti itu ada. Kemudian, kami mempertimbangkan kasus di mana kami membatasi untuk itu sendiri, dan kemudian mendapatkan kontradiksi dengan menggunakan contoh argumen diagonal. Saya tertarik bagaimana buktinya jika kita diberi janji bahwa ? Bagaimana janji , di mana secara fungsional setara dengan ? $T$ $M$ $i$ $T$ $i$ $M$ $i \not = M$ $i \not = M^\prime$ $M^\prime$ $M$

computability undecidability halting-problem bellpeace
sumber

Petunjuk: bahkan jika

tidak diharuskan untuk menjawab pertanyaan tentang dirinya sendiri dengan benar atau bahkan setara dengan

, kita masih dapat mengumpankannya ke

setara dan melihat fungsinya. Karena tidak dapat dihitung apakah

equivalent ekuivalen dengan

tidak akan dapat mengatakan bahwa

memiliki sesuatu yang setara dengan

itu sendiri.

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

M

$M$

Andrej Bauer

@AndrejBauer Apakah ini hanya petunjuk yang Anda berikan kepada saya dan saya harus menyelesaikan masalah saya yang sebenarnya menggunakan petunjuk ini? Saya sedikit bingung, karena Anda rileks masalah dengan mengatakan "tidak memerlukan", di mana dalam pengaturan saya memiliki janji bahwa

tidak akan diberi makan dengan setara

. Pada dasarnya, yang ingin saya lihat adalah segala macam "referensi diri" hal yang membuat masalah tidak dapat diputuskan. Saya berpikir bahwa ini adalah kasus ketika berbicara tentang logika dan ketidaklengkapan.

M

$M$

M^{'}

$M^\prime$

bellpeace

Anda dapat melanggar janji dan memberi makan

apa pun yang Anda suka. Lagipula itu tidak bisa memberitahumu melanggar janjinya. Jika Anda berpikir itu curang, maka saya akan memberi makan

hal-hal yang tidak setara dengan

karena mereka seperti

tetapi dengan semua input digeser oleh

, atau semacamnya.

M

$M$

M

$M$

M

$M$

M

$M$

1

$1$

Andrej Bauer

Sebenarnya, pertanyaan Anda tidak dirumuskan dengan baik. Anda harus menguraikan bukti aktual yang ada dalam pikiran Anda, dan kemudian menentukan secara tepat apa yang ingin Anda hindari. Saya tidak berpikir Anda maksud

, tetapi sesuatu yang lain.

i \neq M

$i \neq M$

Andrej Bauer

Jawaban:

Misalkan HALTS adalah TM yang membaca inputnya sebagai pasangan dan , di mana adalah pengkodean TM dan adalah input apa pun ke TM itu. $M$ $x$ $M$ $x$

Pertanyaan Anda jika apa yang akan terjadi jika kita mengasumsikan menghentikan memecahkan masalah terputus-putus untuk semua masukan sehingga bukan merupakan encoding dari TM yang secara fungsional setara dengan . $\langle M,x \rangle$ $x$ $M$

Saya mengklaim ini menyiratkan kontradiksi. Saya datang dengan ini di tempat, jadi saya menyambut setiap dan semua kritik atas bukti saya. Gagasan buktinya adalah bahwa alih-alih mendiagonalkan sesuatu pada dirinya sendiri, kami membuat dua TM yang saling rekursif yang berperilaku berbeda pada beberapa input (dengan demikian tidak setara secara fungsional), tetapi sebaliknya menyebabkan kontradiksi.

Misalkan dan menjadi dua TM yang saling rekursif (artinya kita dapat mensimulasikan, mencetak, dll, deskripsi di dalam program dan sebaliknya). Perhatikan bahwa kita dapat membuat TM yang saling rekursif dari teorema rekursi. $D_1$ $D_2$ $D_2$ $D_1$

$D_1$ $D_2$ $x$ $|x| < 10$ $D_1$ $D_2$

$x$ $|x| \ge 10$ $D_1$ $\langle D_2, x \rangle$ $D_2$ $D_2$

$x$ $|x| \ge 10$ $D_2$ $\langle D_1, x \rangle$ $D_1$ $D_1$

$x$ $|x| \ge 10$ $D_1$ $D_1$ $D_2$ $D_2$ $D_2$ $D_1$

$D_1$ $x$

$x$ $D_1$ $D_2$ $x$ $10$ $D_1$ $D_2$

Pikiran?

Kurt Mueller
sumber

D_{1}

$D_1$

D_{2}

$D_2$

⟨ D_{1}, D_{2} ⟩

$\langle D_1, D_2 \rangle$

Tanpa itu, buktinya lebih elegan, tapi toh itu terlihat bagus untuk saya dan itulah yang saya butuhkan.

bellpeace

$M'$ $M'$ $M$ $M$ $M'$ $M$

$\langle\,M\,\rangle$ $M$ $H$

$H(\langle\,M\,\rangle, x)$ $x$ $H$ $x$ $H$
$H(\langle\,M\,\rangle, x)$ $M(x)$

$Q$

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

$Q$ $H$ $x=\langle\,Q\,\rangle$ $Q(\langle\,Q\,\rangle)$ $H$

Rick Decker
sumber

i

$i$

M

$M$

Misalkan Anda diberikan janji seperti itu; Saya tahu ini tidak bisa dihitung. Saya telah memperbarui OP.

bellpeace

@ bellpeace:

$\:$ Bagaimana Anda mendefinisikannya?

$\;\;\;\;$

(M, i)

$(M, i)$

i

$i$

M

$M$

1

$1$

M

$M$

i

$i$

0

$0$

M

$M$

M^{'}

$M^\prime$