Bagaimana membuktikan bahwa bahasa bebas konteks menjadi ambigu yang tidak dapat ditentukan?

Saya pernah membaca di suatu tempat bahwa mesin Turing tidak dapat menghitung ini dan karena itu tidak dapat diputuskan tetapi mengapa? Mengapa secara komputasi mustahil bagi mesin untuk menghasilkan pohon parse dan membuat keputusan? Mungkin saya salah dan itu bisa dilakukan?

Kami mengurangi dari Masalah Korespondensi Post . Misalkan kita dapat, pada kenyataannya, memutuskan bahasa .$\{\langle G\rangle\vert G\textrm{ a CFG and }L(G)\textrm{ ambiguous}\}$

Diberikan : Buat CFG berikut G = ( V , Σ , R , S ) : V = { S , S 1 , S 2 } , R = { S → S 1 | S 2 , S 1 → α 1 $\alpha_1, \ldots, \alpha_m, \beta_1, \ldots, \beta_m$$G = (V,\Sigma,R,S)$$V = \{S, S_1, S_2\}$ (di mana σ $R = \{S\rightarrow S_1\vert S_2, S_1\rightarrow \alpha_1 S_1 \sigma_1 \vert \cdots \vert \alpha_m S_1 \sigma_m \vert \alpha_1 \sigma_1 \vert \cdots \vert \alpha_m \sigma_m, S_2\rightarrow \beta_1 S_2 \sigma_1\vert \cdots \vert \beta_m S_2 \sigma_m \vert \beta_1 \sigma_1\vert \cdots \vert \beta_m \sigma_m\}$$\sigma_i$adalah karakter baru yang ditambahkan ke alfabet, misalnya, ).$\sigma_i = \underline{i}$

$w$$S\rightarrow S_1$$S_1$$S_2$$w$

$S\Rightarrow S_1\Rightarrow^* \alpha\tilde{\sigma}$$S\Rightarrow S_2\Rightarrow^* \beta\tilde{\sigma}$$\alpha = \beta$$\alpha$$\beta$$\tilde{\sigma}$

Karenanya, kami telah mereduksi menjadi PCP, dan karena itu tidak dapat dipastikan, kami selesai.

(Beri tahu saya jika saya melakukan sesuatu yang bodoh!)