Dapatkah input ke mesin Turing memiliki panjang tak hingga?

26

Dengan hanya mempertimbangkan alfabet , string yang dapat diberikan sebagai input ke mesin Turing berasal dari himpunan Σ ∗ . Tetapi apakah masuk akal untuk input menjadi string biner yang tak terbatas? Sebagai contoh jika mesin Turing menerima semua string dimulai dengan 0, apakah string biner nol tak terbatas juga milik bahasa yang diterima oleh mesin Turing?Σ={0,1}Σ∗

turing-machines sashas
sumber

Jawaban:

21

Tidak ada masalah dalam menjalankan mesin Turing pada pita yang diinisialisasi dengan string yang tak terbatas, meskipun ini biasanya tidak dipertimbangkan. Kita masih membutuhkan mesin untuk berhenti dalam waktu yang terbatas. Ada juga gagasan perhitungan waktu tak terbatas, yang mungkin sesuai di sini.

Yuval Filmus
sumber
4
Menyelesaikan perhitungan dalam waktu yang terbatas sementara input tidak terbatas tampaknya merupakan tantangan yang sulit.
Tiang
5
@Mast Tidak perlu. Anda tidak bisa membaca seluruh input.
Yuval Filmus
1
@JulesMazur Kata kunci adalah hypercomputation .
Yuval Filmus
3
@ JulesMazur Anda tidak perlu penghitungan hiper apa pun. Program ini bisa terus menulis ke kaset output, dan hasilnya konvergen ke string yang tak terbatas seperti di Mesin Turing Tipe II.
jkabrg
1
Saya pikir Anda mendapat kesulitan jika Anda mengizinkan string infinte sebagai input. Secara khusus set input tidak lagi dapat dihitung, yang mematahkan beberapa bukti.
Taemyr
17

Itulah salah satu fitur dari Type 2 Turing Machines . Mereka digunakan, antara lain, untuk menganalisis komputabilitas fungsi antara bilangan real. Yang lebih menarik lagi, mereka digunakan untuk menganalisis kemampuan komputasi operator seperti integrasi.

Fakta menarik: Integrasi numerik yang tepat dapat dihitung.

jkabrg
sumber
5

Untuk menjawab pertanyaan "apakah ini masuk akal", ini bahkan dapat berguna jika Anda mempertimbangkan mesin Turing yang beroperasi dalam waktu terbatas.

Secara khusus, ini adalah cara yang sangat berguna untuk memikirkan mesin Turing yang bebas awalan . Ini adalah mesin yang himpunan input penghentiannya bebas awalan; yaitu, tidak ada input yang menyebabkan mesin berhenti adalah awalan dari yang lain. Ini setara dalam kekuatan untuk mesin Turing biasa, tetapi hanya jika kita membiarkan mesin Turing untuk memutuskan sendiri input penghentian: yaitu. pengguna tidak tahu input apa yang akan dihentikan mesin (dan ini adalah properti yang tidak dapat ditentukan).

Salah satu cara untuk melihat ini adalah sebagai mesin Turing biasa dengan tape input satu arah yang tak terbatas dengan head tape yang tidak dapat bergerak mundur. Pengguna mengisi kaset dengan bit dan menjalankan mesin. Ini adalah definisi mesin Turing bebas awalan. Jika mesin berhenti, itu pasti hanya membaca sejumlah bit yang terbatas, dan tidak ada awalan dari bagian rekaman itu yang bisa menjadi program, atau mesin akan berhenti di sana sebagai gantinya.

Ini adalah cara yang baik untuk berbicara tentang distribusi probabilitas yang dapat dihitung: pengguna mengisi rekaman dengan bit acak (sumber keacakan mesin), dan mesin mengeluarkan bitstring acak. Himpunan semua mesin Turing tersebut sesuai dengan himpunan distribusi yang dapat dikomputasi (khususnya semimikomputasi semikomputasi rendah).

Keuntungan dari input tak terbatas adalah bahwa kita tidak harus menentukan apa yang dilakukan mesin jika kita memberinya awalan dari program penghentian, yaitu. mesin mencoba membaca melampaui input yang telah kita berikan.

Peter
sumber
2

Bahkan jika Anda tidak memiliki kaset seperti itu, Anda dapat menggunakan mesin Turing lain untuk memproduksinya.

Mesin Turing memiliki akses ke rekaman data yang kosong namun tak terbatas (atau beberapa sumber mengatakan "mesin tersebut hanya memiliki pabrik pita kecil yang terpasang di dalamnya"). Sehingga dapat menginisialisasi dengan beberapa pola data yang dapat diprogram, dan kemudian rekaman itu dapat dikonsumsi sebagai input dari mesin Turing lain.

Tentu saja, jika konten Anda sedemikian rupa sehingga tidak ada algoritma yang dapat ditentukan cara memproduksinya, konten tersebut tidak dapat dibuat oleh mesin Turing.

h22
sumber
6
Saya tidak yakin bagaimana ini menjawab pertanyaan. Dalam kasus apa pun, tidak semua urutan tak hingga dapat dihasilkan oleh mesin Turing, karena ada banyak string tak terhingga pada alfabet mana pun dengan setidaknya dua simbol, sedangkan hanya ada banyak mesin Turing dan input input terbatas untuk diunggulkan.
David Richerby
2

Ada beberapa kasus di mana input tak terbatas dapat dipertimbangkan dan direduksi menjadi aksi dari mesin Turing "standar". Sebagai contoh, pertimbangkan pola terbatas berulang berulang yang ditentukan pada input. Mesin Turing dapat dibuat yang melacak seberapa banyak dari pola tak terbatas ini telah dimodifikasi oleh tindakan tape head saat ini menggunakan jumlah memori / penyimpanan kaset yang terbatas. Dengan kata lain, itu "secara setara mensimulasikan" pola ukuran tak terbatas pada rekaman itu.

Kasus lain di mana "masukan tak terbatas" telah dipertimbangkan adalah analisis kesetaraan Turing / kelengkapan automata seluler. dalam bukti yang kompleks, Cook memperkenalkan konsep yang sekarang disebut oleh beberapa orang sebagai "kesetaraan Turing lemah" dalam mengubah operasi aturan CA 110 menjadi operasi mesin Turing yang dimulai pada pita awal tak terbatas yang ditentukan tetapi dengan pola ukuran terbatas (berulang).

ay
sumber
1
Istilah "input tak terbatas" dan "pengodean terbatas objek tak terbatas" jelas berbeda, dan elementer (setiap bahasa reguler tak terhingga dengan DFA minimalnya adalah contoh). Mereka seharusnya tidak bingung di sini.
Raphael
2
ya DFA dapat digunakan untuk pengkodean yang dijelaskan. sebagai sketsa pita dengan pengkodean terbatas dari string panjang tak hingga (melalui pola terbatas berulang) keduanya berbeda / serupa dalam kemampuan untuk rekaman dengan hanya string terbatas.
vzn
1

Dalam bahasa formal, string adalah, menurut definisi, urutan simbol yang terbatas . Mesin Turing klasik memiliki pita tanpa batas dengan string input yang terbatas. Dengan demikian, sementara tidak ada batasan berapa lama input bisa, itu tidak bisa tanpa batas.

Karena itu, ada banyak mesin alternatif yang bekerja mirip dengan TM tetapi dengan urutan input yang tak terbatas.

Apakah masuk akal untuk memiliki input panjang tak terbatas tergantung pada tujuannya. Ketat dalam konteks Mesin Turing, itu tidak masuk akal (karena tidak mungkin), tetapi dalam konteks Mesin seperti Turing, itu masuk akal dan memiliki banyak aplikasi.

semua orang
sumber
4
Sangat mungkin untuk memiliki string tanpa batas. Memang, ada seluruh cabang teori automata yang berhubungan dengan situasi yang tepat ini. Dan, mengingat bahwa satu-satunya perubahan yang diperlukan untuk definisi mesin Turing untuk memungkinkan mereka berurusan dengan input tak terbatas adalah dengan menghapus kondisi yang mengatakan input harus terbatas, saya tidak setuju bahwa "tidak masuk akal" untuk berbicara tentang mesin Turing dan string tak terbatas.
David Richerby
1
@ DavidRicherby: kami sepertinya setuju. Jangan ragu untuk memberi tahu saya bagaimana saya dapat mengulangi paragraf terakhir untuk membuatnya lebih jelas bahwa itu hanya dalam konteks Mesin Turing asli, klasik, yang tidak tercemar (di mana input menurut definisi terbatas), sehingga tidak masuk akal untuk berbicara tentang input panjang tak terbatas. Segera setelah kami menghapus kondisinya, itu tidak lagi sepenuhnya TM, tapi (apa yang saya sebut) Mesin seperti Turing.
semua orang
1
Saya tidak setuju bahwa perangkat berhenti menjadi mesin Turing hanya karena Anda memulainya dengan hal-hal tak terbatas pada rekaman itu. Mesinnya masih mesin yang sama; Anda baru saja mengubah kondisi awal. Definisi tentang bagaimana mesin Turing berhubungan dengan langauges dari string yang terbatas (mis., Langauges yang dapat decidable atau semi-decidable) adalah dalam hal input yang terbatas tetapi itu tidak berarti bahwa mesin membutuhkannya. Demikian pula, komputer Anda tidak akan berhenti menjadi komputer jika Anda meletakkan tumpukan CDROM di sebelahnya.
David Richerby
1
@ DavidvidRicherby Yah, secara teknis mesin Turing adalah mesin yang membutuhkan input terbatas. Jika Anda mengubah batasan ini dalam definisi, Anda mendefinisikan sesuatu yang lain. Gagasan di balik komputasi masih sama, dalam beberapa hal, tetapi bagaimana Anda mengekspresikan kompleksitas sekarang? Masalah yang sangat berbeda.
Raphael