An Undecidable Property of Recurrent Double Sequences
Prunescu, Mihai
Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, p. 143-151 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$ . ¶ The problem if such recurrent double sequences are ultimately zero is undecidable, even if we restrict it to the class of commutative finite algebras.
Publié le : 2008-04-15
Classification:  recurrent computation,  double sequence,  Turing machine,  undecidable property,  finite commutative algebra,  03D10 
@article{1210859924,
     author = {Prunescu, Mihai},
     title = {An Undecidable Property of Recurrent Double Sequences},
     journal = {Notre Dame J. Formal Logic},
     volume = {49},
     number = {1},
     year = {2008},
     pages = { 143-151},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1210859924}
}

Prunescu, Mihai. An Undecidable Property of Recurrent Double Sequences. Notre Dame J. Formal Logic, Tome 49 (2008) no. 1, pp.  143-151. http://gdmltest.u-ga.fr/item/1210859924/