Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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 Valid HTML 4.01! Valid CSS!