Apakah tesis Church-Turing juga berlaku untuk kecerdasan buatan?

Dengan tesis Church-Turing, mustahil untuk merancang algoritma untuk memutuskan masalah penghentian.

Apakah kata algoritma dalam konteks ini termasuk kecerdasan buatan atau tidak, yaitu apakah tesis Church-Turing juga berlaku untuk kecerdasan buatan?

Apakah mungkin untuk merancang sistem intelijen di masa depan untuk memutuskan masalah ini, atau, dengan tesis Church-Turing, tidak ada AI yang juga akan dapat memutuskan masalah penghentian?

computability artificial-intelligence halting-problem church-turing-thesis M ama D
sumber

Tidak mungkin bahwa sistem AI dapat memutuskan apa pun (dalam pengertian formal, deterministik), tetapi jika itu bisa tentu saja akan melanggar tesis Church-Turing atau keraguan terhadap masalah yang Menghambat. (Yang terakhir jika ditulis dalam bahasa Turing-lengkap, yang sebelumnya dinyatakan.)

Raphael

Mengapa menurut Anda dimungkinkan bahwa kecerdasan buatan mungkin tidak dicakup (atau diperhatikan) oleh Tesis Charch-Turing?

babou

@Babou karena itu termasuk non determinisme, pembelajaran, dll. Ada masalah yang tidak dapat dipecahkan yang memberi kami perkiraan yang sangat baik dari solusi.

M ama D

@Ruprup: tetapi decidability dari beberapa masalah hanya berarti bahwa ada suatu algoritma sedemikian rupa sehingga untuk setiap input yang diberikan dari ruang input masalah, output yang benar akan dihasilkan. Jadi ya, algoritma AI (atau algoritma lainnya) mungkin memberikan perkiraan yang baik untuk masalah penghentian, tetapi ini tidak akan memerlukan decidability.

Roy O.

Jawaban:

Tesis Church-Turing mengatakan bahwa gagasan informal tentang algoritma sebagai urutan instruksi bertepatan dengan mesin Turing. Secara ekuivalen, dikatakan bahwa setiap model perhitungan yang masuk akal memiliki kekuatan yang sama dengan mesin Turing.

Kecerdasan buatan adalah program komputer, yaitu algoritma. Jika tesis Church-Turing berlaku, maka Anda dapat mengimplementasikan algoritma itu pada mesin Turing. Karena mesin Turing tidak dapat memutuskan masalah penghentian mereka sendiri, maka di bawah tesis Gereja-Turing, kecerdasan buatan tidak dapat memutuskan masalah penghentian untuk mesin Turing.

David Richerby
sumber

Di sisi lain, jika AI ditulis pada beberapa jenis komputer analog, atau sirkuit tak beraturan yang tidak seragam, maka masalah Henti untuk mesin Turing adalah kembali ke papan.

DanielV

@DanielV Sirkuit tak terbatas yang tidak seragam tidak membantu. Jika memiliki deskripsi yang dapat dihitung, ia tidak dapat memecahkan masalah penghentian; jika tidak memiliki deskripsi yang dapat dihitung, Anda tidak dapat membangunnya.

David Richerby

Anda tidak dapat membangunnya dengan Mesin Turing. Itu tidak berarti itu tidak berarti bahwa keberadaannya lebih paradoksal daripada 2 titik yang terpisah jarak.

DanielV

@DanielV Bagaimana Anda akan memberi tahu tukang listrik Anda gerbang apa yang akan dimasukkan

n

$n$ th sirkuit jika tidak ada deskripsi yang dapat dihitung?

David Richerby

@DanielV Ada beberapa masalah yang tidak bisa Anda hitung. Anda harus dapat memutuskan kapan Anda telah memecahkan masalah, dan juga apa jawabannya. Dalam hal masalah penghentian, tidak ada cara untuk menentukan bahwa Anda telah memecahkan masalah, apalagi mencari tahu apa jawabannya.

jelas