Vorträge und Posterpräsentationen (ohne Tagungsband-Eintrag):
P. Gillibert:
"Simulating Turing Machines with Invertible Mealy Automata";
Vortrag: MEALYM Final Event,
Université Paris-Diderot (eingeladen);
10.07.2017
- 13.07.2017.
Kurzfassung englisch:
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.
Schlagworte:
Turing Machines Invertible Mealy Automata
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.