# How can one implement universal turing machines on general languages?

In most resources, I found that the statement of universal Turing machines assumes that the input alphabet for all Turing machines $$T$$ is given to be identical (e.g. $$\{0,1\}$$) as this gives enough complexity to encode every other finite alphabet with little overhead.

However, I was wondering how one would formalize this approach to all Turing machines. The obvious choice for me is that together with an encoding $$d: \{T |\; T \text{is a turning machine} \} \rightarrow \Sigma^*$$ of the set of Turing machines one should also give an encoding of alphabets $$\tilde{d}: \{\Gamma | \;\Gamma \,\text{is a finite alphabet} \} \rightarrow \Sigma^*$$ and reformulate the statement of universality such that $$L(U) = \{ (d(T), \tilde{d}^*(x)) |\; T \;\text{a Turing machine}, x \in L(T)\}$$, where $$\tilde{d}^*$$ just refers to the application of $$\tilde{d}$$ to each character.

Firstly is this the correct approach? Secondly, this left me wondering what computational power one could hide in this extra encoding (and the encoding $$d$$ in general). E.g. what effect would it have if instead of acting on each character separately $$d^*$$ could act on the whole string i.e. define $$\tilde{d}^* : \{\Gamma^*\} \rightarrow \Sigma^*$$ or something similar?

Does anyone have any resources on this kind of question and in what cases is it possible to make statements about the computational power of $$d$$, $$\tilde{d}$$?

Any help is greatly appreciated.

• I think you can use whatever "reasonable" encoding you want; for example: simply order each element of gamma $\Gamma$, and then map each element to the binary representation of its index in the order. To avoid any "trouble" with lengths, just use a prefix free encoding, for example $x_1 x_2 ... x_n \in \Gamma \to 1^n0x_1 x_2 ... x_n$. Furthermore you can encode the whole Turing machine in such a way that every element of $\Sigma^*$ represents a valid TM. And clearly - without further restrictions - in $\tilde{d}^*$ you can hide every problem (even undecidable ones). May 25 at 12:47
• Turning machines? May 25 at 20:47