On the dimension of the solution space of linear difference equations over the ring of infinite sequences

Abstract

For a linear difference equation with the coefficients being computable sequences, we establish algorithmic undecidability of the problem of determining the dimension of the solution space including the case when some additional prior information on the dimension is available.

arXiv commentIn memory of Marko Petkovšek