Talks and Poster Presentations (without Proceedings-Entry):
P. Gillibert:
"Simulating Turing Machines with Invertible Mealy Automata";
Talk: MEALYM Final Event,
Université Paris-Diderot (invited);
2017-07-10
- 2017-07-13.
English abstract:
From any Turing Machine, with a one-direction infinite tape, we construct an invertible Mealy Automaton. The corresponding automaton group simulates the Turing Machine in the following sense: given an entry word there is an (explicitly constructed) element of the group so that the Turing Machine stops on this entry if, and only if, the order of the element is finite.
In particular, considering an automaton group constructed from a universal turing machine, there is no algorithm which decides whether or not an element is of finite order.
Keywords:
Turing Machines Invertible Mealy Automata
Created from the Publication Database of the Vienna University of Technology.