Computability in Europe 2008
Logic and Theory of Algorithms

## Regular Talk: Polynomial iterations over finite fields

Edit abstract data

 THIS TALK HAS BEEN CANCELLED!!! Speaker: Mihai Prunescu

### Abstract

Consider the following natural algorithm: given a finite field $\mathbb F$ and a
polynomial $f \in \mathbb F[x,y,z]$ one produces the double sequence $(a_{i,j})$
defined by $a_{0,j} = a_{i,0} = 1$ und $a_{i,j} = f(a_{i,j-1},a_{i-1,j-1}, a_{i-1, j})$. If the polynomials $f$ are linear, self-similarity arises. On the
other hand, the class of double sequences $(a_{i,j})$ generated by symmetric
polynomials $f(x,z)$ over arbitrary finite fields is Turing complete.



 websites: Arnold Beckmann 2008-06-11