Halting problem

Bahasa H = \{ \langle M,w \rangle: M \, \text{halt jika diberikan masukan} \, w \} merupakan anggota SD-D.

Ada dua hal yang perlu dibuktikan: H \in SD dan H \notin D.

Bukti H \in SD.

Pembuktikan H merupakan bahasa SD tidak sulit. Diberikan masukan \langle M,w \rangle, mesin Turing kita bisa mensimulasikan program M dengan masukan w. Di akhir proses, jika ternyata berdasarkan simulasi program M halt, maka mesin Turing kita bisa langsung halt yes. Jika program M tidak halt, mesin Turing kita tidak akan halt yes. Mesin Turing kita ini sudah bisa dikatakan semi-decide H karena:

  • jika \langle M,w \rangle \in H, maka simulasi akan halt, dan mesin Turing kita akan halt yes,
  • jika \langle M,w \rangle \notin H, mesin Turing kita tidak akan halt yes.

Bukti H \notin D.

Sekarang, yang perlu ditunjukkan adalah H \in \neg D, yaitu bahasa yang tidak decidable. Hal ini akan dibuktikan dengan kontradiksi. Asumsikan H \in D, maka ada mesin Turing hipotesis, biasanya disebut Oracle, O yang bisa men-decide H.

Sekarang, misalkan ada mesin Turing T(x) yang bekerja sebagai berikut:

  • Simulasikan O dengan masukan \langle x,x \rangle.
  • Jika O menjawab yes pada \langle x,x \rangle, loop.
  • Jika O menjawab no, T halt.

Sekarang, misalkan T diberikan input \langle T \rangle, yaitu encoding deskripsi dari T itu sendiri.  Kita observasi keluaran dari T(\langle T \rangle):

  • Jika O menjawab yes, berarti T akan halt dengan masukan \langle T \rangle. Namun, pada implementasinya T loop. Jadi, tidak mungkin.
  • Jika O menjawab no, berarti T tidak halt dengan masukan \langle T \rangle. Namun, pada implementasinya, justru T halt.

Perhatikan bahwa program T merupakan program yang valid. Jadi, asumsi awal kita tidak mungkin terpenuhi. Dengan demikian, oracle O yang men-decide H tidak ada. Terbukti.

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s