Fungsi apa yang tidak dapat dihitung oleh Sistem F?

Dalam artikel wikipedia ini tentang Turing Completeness disebutkan bahwa:

Kalkulus lambda yang tidak diketik adalah Turing lengkap, tetapi banyak kalkulus lambda yang diketik, termasuk Sistem F, tidak. Nilai dari sistem yang diketik didasarkan pada kemampuan mereka untuk mewakili sebagian besar program komputer sambil mendeteksi lebih banyak kesalahan.

Apa contoh dari total fungsi komputasi yang tidak dapat dihitung oleh sistem F ?

Selain itu, karena hindley-milner adalah:

Pembatasan Sistem F

karena kenyataan bahwa:

pengecekan tipe tidak dapat ditentukan untuk varian Curry-style dari Sistem F, yaitu, yang tidak memiliki anotasi pengetikan yang eksplisit.

Apakah ini berarti bahwa kalkulus lambda yang mendasari sistem tipe hindley-milner tidak lengkap juga?

Jika ini benar, karena haskell jelas turing lengkap dan kita tahu bahwa dasarnya adalah kalkulus lambda dan sistem tipe hindley-milner, fitur apa yang tidak ada dalam kalkulus lambda ditambahkan untuk membuat haskell turing lengkap?

$F$$\mathbb{N}\rightarrow\mathbb{N}$$\mathbb{N}$$\forall X.\ X\rightarrow (X\rightarrow X)\rightarrow X$$\mathbb{N}\rightarrow\mathbb{N}$$\mathrm{HA}_2$

$T$$F$$\mathrm{eval}:\mathbb{N}\rightarrow\mathbb{N}$$t$$F$$t$. Buktinya melibatkan varian dari trik diagonalisasi yang digunakan untuk keraguan masalah penghentian. Andrej menjelaskannya dengan indah di sini .

$\lambda$$F$ $\lambda$

$Y$$Y$

Perhatikan ada fitur lain yang membuat Haskell Turing lengkap, tetapi mereka biasanya tidak dianggap sebagai bagian dari bahasa inti, misalnya referensi ke fungsi, tipe data tidak terbatas, dll.

Agak keliru untuk mengatakan bahwa sistem pengetikan Haskell adalah "sistem tipe hinley-milner". Tipe-tipe Haskell jauh lebih kuat, termasuk, di antaranya, tipe-tipe yang lebih tinggi. Memang sistem pengetikan sangat kuat sehingga Anda dapat menanamkan bahasa pemrograman Turing-lengkap dalam sistem pengetikan, lihat di sini . Ini bukan satu-satunya alasan kekuatan Haskell, Cody telah menyebutkan beberapa yang lain.