Mengapa keadaan FSM secara tradisional dilambangkan

13

Sambil mengajar bagaimana menerapkan FSM menggunakan sirkuit logis sinkron, saya melihat sebuah kebetulan yang menarik: baik di dunia CS teoritis, dan di dunia teknik listrik, "negara" biasanya dilambangkan (dan ruang negara Q ). Saya pertama kali bertanya pada EE.sx , tetapi kemudian ketika meneliti sedikit topik ini, saya menemukan bahwa bahkan 1936 kertas asli Turing menggunakan q 1 . . q n untuk menunjukkan negara bagian mesin Turing.qQq1..qn

Jadi saya bertanya-tanya: Kapan konvensi ini kembali ke, dan mengapa "negara" dilambangkan ?q

automata-theory ho.history-overview Gyom
sumber
1
Jika saya harus menebak, saya akan mengatakan adalah kependekan dari "konfigurasi" (karena c dan k sudah terikat ke "konstan"). Tapi itu hanya dugaan. qck
Jeffε
1
pertanyaan menarik tentang kaitan historis antara mesin Turing dan jawaban terpilih automata ini menyangkal adanya hubungan historis langsung antara banyak teori automata dan karya Turings 1936. jawaban terbawah menunjukkan kesamaan yang hampir identik dari konsep tabel negara.
vzn
1
Saya pikir Anda mungkin mendapatkan jawaban yang lebih baik jika Anda mempostingnya di MathOverflow. Mereka memiliki lebih banyak ahli teori komputasi. Tempat lain yang baik untuk bertanya ini adalah milis FOM yang memiliki banyak pakar tentang sejarah komputabilitas.
Kaveh

Jawaban:

6

Dalam makalahnya tahun 1936 "PADA ANGKA KOMPUTABEL, DENGAN APLIKASI KEPADA MASALAH ENTSCHEIDUNGSPROBLEM" , Alan Turing menulis:

"Kita dapat membandingkan orang dalam proses menghitung bilangan real dengan mesin yang hanya mampu sejumlah kondisi terbatas q1, q2, .... qR yang akan disebut" konfigurasi-m "

Jadi dia menekankan fakta bahwa mesin itu memiliki jumlah atau jumlah yang terbatas, tidak jelas. Bagi saya, ini adalah referensi ke istilah Quanta yang digunakan dalam fisika untuk menunjukkan fenomena yang berubah tidak terus-menerus tetapi oleh "lompatan" atau "kuanta". Dalam artikelnya tahun 1950 "Komputasi Mesin dan Kecerdasan" Alan Turing lebih eksplisit tentang "lompatan" berbicara tentang "lompatan tiba-tiba":

"Komputer digital yang dibahas pada bagian terakhir dapat diklasifikasikan di antara" mesin diskrit. "Ini adalah mesin yang bergerak dengan lompatan tiba-tiba atau klik dari satu kondisi yang cukup pasti ke kondisi lainnya."

Jadi saya berpikir bahwa Alan Turing menggunakan q daripada s untuk menyatakan keadaan mesin untuk menekankan fakta bahwa mesin keadaan hanya dapat dalam satu set nilai diskrit dan terbatas seperti kuanta dalam fisika. Dan sejak itu, notasi yang sama umumnya digunakan.

Tarik FDIL
sumber
2

Saya tidak yakin tetapi saya membaca bahwa Q berarti Quantum. Karena kita tahu automata bekerja dalam kerangka waktu diskrit. Otomat selalu tetap dalam keadaan tertentu dalam kondisi terbatas, dan bahkan dimulai dengan keadaan awal q 0 . Automaton juga tidak dapat berada di lebih dari satu keadaan pada waktu kapan pun. Kata kuantum berasal dari fisika yang berarti kuantitas, jumlah atau angka.

Grijesh Chauhan
sumber