Bisakah FSA menghitung?

11

Ini mungkin pertanyaan konyol. Tampak jelas bahwa FSA, karena terbatas, hanya dapat menghitung jumlah simbol dalam string inputnya hingga sejumlah yang dibatasi oleh jumlah negara bagian. Tapi sekarang anggaplah kita melengkapi FSA dengan kemampuan output (misalnya pencetakan). Maka akan sangat mudah untuk membangun mesin yang mampu mencetak satu simbol untuk setiap simbol yang dibacanya. Apakah itu dihitung sebagai penghitungan? Jika tidak, mengapa tidak?

Untuk menempatkannya dalam bentuk FST sebagai gantinya: Saya menganggap bahwa tidak mungkin untuk membangun FST yang mampu memetakan string yang panjangnya sewenang-wenang ke representasi biner (yaitu angka dalam sistem angka base-2) dari panjangnya. Tapi tentu saja sepele untuk membangun FST yang mampu memetakan string yang panjangnya sewenang-wenang ke string kata nol (atau yang) dengan panjang yang sama. Tapi itu bisa dihitung sebagai penghitungan, tidak bisa, karena apa yang dilakukan FST adalah membangun representasi dari panjang inputnya. Representasi yang agak aneh, tapi tetap representasi, bukan?

automata finite-automata Torbjörn
sumber

1

Jadi, Anda benar-benar mengajukan pertanyaan "apa yang menghitung?" Bagi saya itu tidak terdengar seperti ilmu komputer. Ini akan menjadi ilmu komputer jika pertanyaan Anda adalah "untuk definisi penghitungan ini, dapatkah FSA menghitung?".

Sasho Nikolov

8

Pertanyaan ini agak kabur, jadi inilah jawaban yang tidak jelas: Menerjemahkan unary ke unary tidak persis menghitung, karena mesin tidak benar-benar "tahu" berapa ukuran input "pada akhirnya".

Anda menyadari ini, tentu saja, itulah sebabnya Anda mempertanyakan fakta bahwa itu memang berhitung.

Menerjemahkan dari unary ke biner, bagaimanapun, tampak seperti operasi yang jauh lebih maju, karena tidak hanya melibatkan penghitungan, tetapi juga melibatkan aritmatika.

Jadi, mungkin gagasan yang lebih tepat untuk dilihat, alih-alih menghitung, adalah membandingkan . Yaitu, diberi dua angka (dalam unary) dan , tentukan jika . $1^n$ $1^m$ $n=m$

Kemampuan untuk melakukan perbandingan ini adalah apa yang menimbulkan bahasa terkenal non-reguler . Dan ketidakmampuan seorang NFA untuk menghitung adalah apa yang membuat bahasa ini tidak teratur. $\{a^nb^n: n\ge 0\}$

Menariknya, bahasa ini adalah CFL. Dan memang, model automata yang sesuai - PDA, memang memiliki kemampuan untuk melakukan perbandingan terbatas.

Ketika Anda berbicara tentang membandingkan, transduser tidak lagi memberi Anda kekuatan tambahan, jadi pertanyaannya terselesaikan dalam pengertian itu.

Catatan tambahan: sepenuhnya informal, kemampuan untuk membandingkan dua angka sering dapat digunakan untuk mensimulasikan mesin 2-counter Mesin Minsky , yang setara dengan TM.

Shaull
sumber

4

Tidak. Automata negara terbatas tidak masuk hitungan. Mereka mungkin melakukan hal-hal yang terlihat seperti itu, tetapi mereka tidak dapat menghitung. Mereka bahkan dapat melakukan sedikit perhitungan (terprogram) (seperti menentukan apakah angka biner dapat dibagi tiga ) tetapi itu tidak termasuk hitungan.

Sebuah cerita kecil Anda berada di sebuah kotak persegi panjang besar di kota yang terkenal. Penduduk setempat memberi tahu Anda bahwa alun-alun sebenarnya adalah kotak. Jika Anda dapat menghitung Anda memeriksa apakah jumlah ubin horisontal dan vertikal cocok dengan menghitung ubin di sepanjang sisi kotak. Jika Anda tidak dapat menghitung, Anda masih dapat memverifikasi klaim: mulai dari sudut dan berjalan secara diagonal. Jika Anda benar-benar mencapai sudut yang berlawanan, Anda memiliki kotak.

$a$ $b$ $a$ $b$

$L$ $T$ $D_2$ $L = T^{-1}(D_2)$ $T$ $L$ $T$ $L$ $D_2$ $w\in T^{-1}(D_2)$ $T(w) \in D_2$

$D_2$

Hendrik Jan
sumber

0

$0$

2^{n!}

$2^{n!}$

n

$n$

N

$\mathbb{N}$

2^{n!}

$2^{n!}$

Tetapi cara FSA biasanya disajikan, mereka hanya "diizinkan" untuk mengatakan "ya" (diterima) atau "tidak" (tidak diterima). Mengingat ini, tidak ada yang bisa membangun FSA yang diperhitungkan. Jika kita mengizinkannya untuk melaporkan (misalnya mencetak) status (jumlah) yang ada saat berakhir, maka ia dapat menghitung, tetapi hanya sampai batas yang diberikan oleh jumlah negara. Tetapi jika DO kita mengizinkannya untuk mencetak, maka itu sepele untuk membangun satu negara FSA yang mencetak (katakanlah) 1 setiap kali itu membaca simbol dari string input, sehingga melaporkan hitungan dalam representasi penghitungan. Apa yang salah dengan ide ini?

Torbjörn

Dan jika kita lupa tentang pelaporan / pencetakan, dan berpikir dalam hal representasi internal sebagai gantinya, FSA dapat menghitung simbol dalam string, tetapi tidak dalam panjang yang sewenang-wenang. Single state FSA tentu saja tidak dapat dihitung sama sekali.

Torbjörn

k

$k$

1

@Shaull: Terima kasih atas jawaban Anda! Saya baru di StackExchange dan tidak tahu bagaimana mengomentari jawaban, jadi saya memilih untuk menulis jawaban, dengan harapan saya dapat dimaafkan.

Hmm, bagi saya kelihatannya seorang shepard menghitung domba-dombanya dengan menuliskan tanda pada selembar kertas untuk setiap domba yang ia lihat, atau seorang tahanan menghitung hari-hari di penjara dengan menuliskan tanda di dinding, sedang menghitung. Mengapa n tidak menandai pada selembar kertas atau di dinding sebagai representasi dari angka n? Bukankah itu yang disebut representasi penghitungan? AFAICS sama sekali tidak kalah dengan (katakanlah) representasi biner, kecuali bahwa ia menggunakan lebih banyak ruang.

Saya kira untuk Anda, "tahu" berarti bahwa ia memiliki representasi internal hitungan pada akhirnya. Maka, tentu saja, jelas bahwa FSA FST tidak dapat menghitung panjang string yang arbitrer. Tetapi jika kita tidak memerlukan pengetahuan dalam pengertian itu, tetapi hanya menuntut agar FSA atau FST harus dapat memberitahukan hasilnya kepada pengamat eksternal, maka bagi saya tampaknya menyajikan hitungan dalam format penghitungan harus ok.

Selain itu, jika FSA dilengkapi dengan input dan output tambahan, maka pada prinsipnya harus dapat menggunakan lingkungan eksternal sebagai memori baca / tulis, dan dengan demikian sekuat mesin Turing. Baik?

Terima kasih telah mengemukakan kasus perbandingan. Sekarang, tampaknya menjadi kasus bahwa jika kita mengangkat persyaratan representasi internal, dan kita hanya mengharuskan mesin mampu menyajikan hasilnya kepada pengamat eksternal, maka kita dapat dengan mudah membangun FSM yang dapat menghasilkan semacam presentasi grafis dari hasilnya. Misalkan FSM, setelah dibaca "aaaaaabbbbbb" aja

000000
000000

kemudian, karena bilah memiliki panjang yang sama, FSM telah menerima string "aaaaaabbbbbb". Dua batang dengan panjang yang sama berarti "ya", panjang yang berbeda berarti "tidak".

Saya kira saya membengkokkan aturan, tapi itulah yang saya inginkan karena saya tertarik pada asumsi yang kurang lebih tersirat yang dibuat di bidang linguistik matematika.

Torbjörn
sumber

F S A_{W O C}

$FSA_{WOC}$

{a^{n} | n is prime}

$\{a^n | n \mbox{ is prime }\}$

Saya pikir perbedaan antara contoh yang Anda berikan dan FST-output adalah bahwa gembala dapat membaca baris setelah ditulis, sedangkan FSM tidak bisa. Hal yang sama berlaku untuk membandingkan.

Shaull

Anda dapat berkomentar dengan mengklik tautan "tambahkan komentar" di bawah tulisan apa pun.

Raphael

FSA yang dibuat untuk menghitung kawanan dapat menghitung kawanan itu. Tidak ada FSA yang dikonstruksi dapat menghitung kawanan apa pun. Pertanyaan mendasarnya adalah apakah gembala hanya tahu cara menghitung cukup jauh untuk setidaknya menghitung kawanannya sendiri, atau dapat menggunakan seluruh jajaran bilangan asli. Dalam pengalaman saya, kita manusia harus secara eksplisit membuat transisi antara dua kemampuan di beberapa titik dalam pendidikan matematika kita.

reinierpost

1

FSM dapat "menghitung" dalam rentang yang terbatas / sejumlah langkah yang ditandai oleh transisi negara. Namun, mereka tidak dapat menghitung melewati sejumlah langkah yang terbatas.

ada perasaan di mana mesin seperti FSA dapat menghitung. mesin yang berhubungan erat disebut Finite State Transducer . transduser memang bisa dihitung dalam arti input dan output "piped". transduser tunggal dapat mengambil urutan input (katakanlah dalam biner) dan "transduce" ke urutan output yang bertambah. kemudian satu "rantai" transduser count-by-1 (identik), masing-masing menambah inputnya dengan 1 dan mengeluarkannya. ini juga seperti "algoritma streaming" yang belum sempurna .

vzn
sumber

lebih detail: transduser dapat meningkatkan fungsi "lsb" menjadi "msb" yaitu "bit sig paling" ke "bit sig paling" menggunakan logika yang mirip dengan penambah penuh EE .

vzn

Transduser dalam kondisi terbatas tampaknya belum banyak dipelajari. ada aplikasi lain yang menarik untuk dugaan collatz dalam menciptakan mesin yang menghitung iterates. siapa pun yang tertarik pada teori / diskusi kontak plz lanjut saya dalam chatting atau pada saya blog .

vzn

Bisakah FSA menghitung?

Jawaban: