Undecidability of restricted uniform recurrence equations
type: Item
instance of: scholarly article
title: Undecidability of restricted uniform recurrence equations
zbMATH Open document ID: 0848.11062
published in: Acta Informatica
publication date: 1995-11-19T00:00:00Z
review text: A system of recurrence equations is said to be computable if and only if none of its variable instances depends on itself and each of them depends only on finitely many variable instances. The computability of systems of recurrence equations is considered to be the first point of examination when trying to implement an algorithm. In general, when the index domains of a system are allowed to be unbounded and distinct, the computability of such systems may be undecidable. The results presented in this paper essentially demonstrate that the computability of uniform systems of recurrence equations is undecidable even if the number of indices, the number of recurrence equations, the number of variables, and the number of different index domains are bounded by a constant. In particular, we show that the computability of systems of recurrence equations is undecidable for \(\bullet\) affine systems with three indices, one variable, three equations, and three index domains, \(\bullet\) uniform systems with four indices and five index domains, and \(\bullet\) uniform systems with six indices, one variable, seven equations, and seven index domains. The parameters which are not fixed in all the restricted versions are first, the integers involved in the index manipulations, and second, the number of variable instances used in an equation.
Mathematics Subject Classification ID: 11U05
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 814153
zbMATH Keywords: undecidability
zbMATH Keywords: system of recurrence equations
zbMATH Keywords: computability
author: Egon Wanke
MaRDI profile type: Publication
full work available at URL: s002360050053
OpenAlex ID: W1971232640
cites work: Q3862379
cites work: The Organization of Computations for Uniform Recurrence Equations
cites work: Q4943600
cites work: The mapping of linear recurrence equations on regular arrays
cites work: Q3818127
cites work: Computability of recurrence equations
DOI: 10.1007/S002360050053
description: scientific article; zbMATH DE number 814153