An undecidable property of recurrent double sequences
Consider a finite algebra \((A,*,0,1)\), where \(A\) is a finite set, \(0\) and \(1\) are two constants in \(A\), and \(*:A\times A\to A\) is a binary operation. Define \(a:\mathbf N\times\mathbf N\to A\) as follows: If \(i=0\) or \(j=0\) then \(a(i,j)=1\), otherwise \(a(i,j)=a(i,j-1)*a(i-1,j)\). The recurrent double sequence \(a(i,j)\) is said to be ultimately zero if \(a(i,j)=0\) whenever \(i>0\), \(j>0\) and \(i+j\) is sufficiently large. The author proves that it is undecidable if the recurrent double sequence defined by a commutative finite algebra is ultimately zero. The modern formulation of Rice's theorem is used in the proof.
- Self-similar carpets over finite fields
- A two-valued recurrent double sequence that is not automatic
- RECURRENT DOUBLE SEQUENCES THAT CAN BE PRODUCED BY CONTEXT-FREE SUBSTITUTIONS
- Recurrent two-dimensional sequences generated by homomorphisms of finite abelian p-groups with periodic initial conditions
- The Thue-Morse-Pascal double sequence and similar structures
This page was built for publication: An undecidable property of recurrent double sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q929632)
