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.

  • 3
    $\begingroup$ 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). $\endgroup$ May 25 at 12:47
  • 2
    $\begingroup$ Turning machines? $\endgroup$ May 25 at 20:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.