## Abstract

We introduce computable actions of computable groups and prove the following versions of effective Birkhoff’s ergodic theorem. Let Γ be a computable amenable group, then there always exists a canonically computable tempered two-sided Følner sequence (F_{n})_{n≥ 1} in Γ. For a computable, measure-preserving, ergodic action of Γ on a Cantor space { 0 , 1 } ^{ℕ} endowed with a computable probability measure μ, it is shown that for every bounded lower semicomputable function f on { 0 , 1 } ^{ℕ} and for every Martin-Löf random ω∈ { 0 , 1 } ^{ℕ} the equalitylimn→∞1|Fn|∑g∈Fnf(g⋅ω)=∫fdμholds, where the averages are taken with respect to a canonically computable tempered two-sided Følner sequence (F_{n})_{n≥ 1}. We also prove the same identity for all lower semicomputable f’s in the special case when Γ is a computable group of polynomial growth and F_{n} := B(n) is the Følner sequence of balls around the neutral Γ.

Original language | English |
---|---|

Pages (from-to) | 1269-1287 |

Number of pages | 19 |

Journal | Theory of Computing Systems |

Volume | 62 |

Issue number | 5 |

DOIs | |

Publication status | Published - 2018 |

## Keywords

- Computable actions of groups
- Effective ergodic theorems