0
$\begingroup$

First, I learned this based on these facts:

  1. Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$.
  2. Any computation rules that can use to simulate any possible TM is called Turing-Complete.
  3. Universal TM (UTM) is TM that is Turing-Complete.

Then, the question begins:

  • If we have 7-tuple Notation of any U that is UTM, Is there an algorithm to find initial tape content P that U to simulate any TM T with any I input(s)? If it exists, Does it based on each U or pattern of U? If it does, give me some example(s)? If it does, explain the algorithm?
  • Since all possible computations can be done with TM, Is there an algorithm to make TM simulate any algorithm P written in any language? If it exists, give me some example(s)?
  • If both questions above exist the algorithm, Why don't we just make a single UTM U and use it to program itself then do every possible computation?
$\endgroup$
1
$\begingroup$

With regards too your first question I would take a different easier to understand route. Firstly you should note that most programming languages are (theoretically) Turing-Complete (which implied that for a program written in some programming language like C or Python you could transform it into a TM or vice versa).

I'm sure that you heard of the concept "interpreter". It's a program that takes a script as input and runs it (e.g. the python interpreter). You can probably write a simple interpreter yourself (great tutorial).

Now notice that your interpreter could be converted to a TM which takes programs as inputs and runs them, thus you could construct a UTM, and the input would be e.g. a python script.

With regards to your second question: as I mentioned most programming languages used today are (theoretically) Turing-Complete meaning that you could transform any Turing-Machine too a program in this language. The straight forward approach, which works in most object oriented languages is just to model a Turing-Machine (using e.g. a string as tape and an int to remember where on the tape your head is and so on...simple example). Algorithms that convert one program from one language to another are called transpilers.

I think I don't fully understand your last question. Of course you could plug a UTM into itself. It's like writing a python interpreter in python. The "problem" is that simulation comes at a cost. Generally if you simulate a UTM on a UTM the complexity of some operations increases.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The last question states that If there is a UTM then why don't we design cpu/ram/... as a UTM. For example, a mechanic UTM. $\endgroup$ – mwit30 room8 Aug 26 at 1:03
  • 1
    $\begingroup$ CPUs are sort of UTMs (They have finite memory which makes them less powerful than TMs). You give your cpu a program in the form of a list of instructions and it executes the program on any given input. You can express a TM as a list of instructions thus a typical CPU is a UTM ( if we neglect the finite memory). $\endgroup$ – plshelp Aug 26 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.