Bisakah mesin dua penghitung memutuskan

Dapatkah mesin standar dua penghitung ( ) dengan instruksi berikut: $c_1,c_2$

1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

tentukan bahasa berikut:

L = {n^{2} ∣ n \geq 1}

$L = \{ n^2 \mid n \geq 1 \}$

(input awalnya dimuat di konter ) ?. $c_1$

Apakah ini masih merupakan masalah terbuka? (lih. Rich Schroeppel, "Mesin Dua Penghitung Tidak Dapat Menghitung " [1972]) $2^N$

fl.formal-languages counter-automata Marzio De Biasi
sumber

Saya mencoba untuk memahami hasil yang paling penting dari kertas dan saya benar-benar terkejut dengan Arithmetic Progresi Teorema pada halaman 12. Misalkan

adalah pembagi ganjil terbesar dari

. Lalu apa yang akan

dan

? Mungkin saya salah paham tentang sesuatu di suatu tempat ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Sekarang saya akan melihatnya, tetapi apakah Anda yakin bahwa "pembagi ganjil terbesar N" dapat dihitung dengan 2cm?

Marzio De Biasi

@domotorp: omong-omong saya menanyakan pertanyaan yang sama juga di mathoverflow , tetapi tidak mendapatkan ide baru

Marzio De Biasi

Saya pikir jika Anda terus membagi N dengan 2 sampai Anda bisa, Anda akan mendapatkan pembagi ganjil terbesar dan ini harus langsung dilakukan.

domotorp

Ok, saya pikir jika

(dengan

ganjil) dan

adalah kekuatan terbesar dua lebih besar dari

, kita dapat mengatur

. Secara informal jika

memiliki bit

, maka Anda dapat dengan aman memperluas bit paling signifikan dari

menambahkan

N = 2^{k} x

$N = 2^k x$

x

$x$

2^{i}

$2^{i}$

N

$N$

2^{l}

$2^{l}$

x

$x$

D = 2^{i - 1}

$D=2^{i-1}$

M = 2^{l - 1}

$M = 2^{l-1}$

N

$N$

i

$i$

N

$N$

j 2^{i - 1}

$j 2^{i-1}$ dan hasilnya akan berubah oleh

j 2^{l - 1}

$j 2^{l-1}$

Marzio De Biasi

Jawaban:

Masalahnya telah diselesaikan di:

Oscar H. Ibarra, Nicholas Q. Trân, Catatan tentang program sederhana dengan dua variabel, Ilmu Komputer Teoritis, Volume 112, Edisi 2, 10 Mei 1993, Halaman 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Mari menjadi kelas bahasa diakui oleh mesin dua-counter. $TV$

Teorema 3.3 : Untuk bilangan bulat tetap , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Catatan: aneh di koran Ibarra & Tran

Teorema 3.4 Misalkan adalah fungsi total dengan rentang tak hingga dan sedemikian sehingga hubungan untuk semua tidak berlaku untuk triple $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ ; maka tidak dapat dihitung oleh mesin dua-counter. $(a,b,c)$ $f$

terbukti dan penulis mengatakan bahwa itu diturunkan dalam bentuk yang sedikit berbeda di:

IM Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), Rusia, Aljabar dan Logika 1 (1963) 42-51

tapi jangan mengutip makalah Rich Schroeppel (1972) di mana teorema itu juga diturunkan ... :-)

Marzio De Biasi
sumber

Saya tidak yakin bahwa aneh bahwa sebuah makalah berusia dua puluh tahun tidak dikutip: mungkin penulis tidak mengetahuinya dan wasit juga tidak.

David Richerby

@DavidRicherby: Saya ingin tahu melihat bagaimana teorema di Schroeppel (1972) berbeda dari yang sesuai di Barzdin (1963) :-) ... tapi saya tidak punya akses ke kertas Barzdin

Marzio De Biasi