An undecidable property of recurrent double sequences (Q929632): Difference between revisions

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.