Could a Universal Turing machine be set up so that it is able to 'reprogram' itself to 'behave' like any specific Turing machine without using some 'outside' source of info to cause it to do this?

  • 7
    $\begingroup$ The universal Turing machine is a concept that is defined by multiple websites and by any textbook on the theory of computation. There seems little point in somebody typing out all that stuff again. What definitions have you read and what specifically didn't you understand about them? $\endgroup$ – David Richerby Jul 22 '15 at 5:56
  • $\begingroup$ So a UTM can 'mimic' any other algorithm only after the state transition table is encoded in the input to the UTM. If an algorithm is not computable there is no Turing Machine that can 'simulate it'. Is there a state transition table for a UTM? $\endgroup$ – 201044 Jul 23 '15 at 1:10
  • $\begingroup$ @201044 Computability is the property of mathematical function (not of algorithm). A function is computable if there exist an algorithm to compute it i.e there exist some Turing machine to compute it. CPU is like a UTM where the CPU change the states based on the instruction read from memory. $\endgroup$ – Ankur Jul 23 '15 at 3:54
  • $\begingroup$ That's an interesting thought ; the CPU is like a UTM. $\endgroup$ – 201044 Jul 25 '15 at 10:56

Turing machine is a formalized representation of the concept of algorithm (aka effective method). Why do we need a formalized representation? So that we can reason precisely about the thing and that's why Turing created this formalized representation to answer Hilbert question of decision problem.

A Universal Turing machine is a machine that can simulate any Turing machine i.e An algorithm that can simulate any algorithm. Intuitively it may seem that this algorithm that can simulate any other algorithm must be really complex BUT it turns out that this algorithm is really the dumbest algorithm possible. In Turing machine the "state transition table" is the logic of the algorithm and the state of the tape is the Input and Output of the algorithm. Now if I want to create a Turing machine that can simulate any algorithm than I could try to design a state transition table that has logic for every possible algorithm (e.g sorting, hashing, compression and on and on ...) but that is not feasible as the number of all algorithms is infinite. What about if we encode this state transition table as the input and the state transition table of the machine is designed such a way that its logic depends on the state transition table encoded in the input. In this way this single and quite simple Turing machine can simulate any other Turing machine.

So if an algorithm can not be 'inputted' to the Universal turing machine it is not computable , is this true?

I guess by 'inputted' you mean that the algorithm cannot be encoded as input to the UTM. Any algorithm can be encoded as input to the UTM the only requirement is that you should "know the algorithm first". If you don't have the algorithm then obviously the function is not computable .... yet :)

  • 1
    $\begingroup$ Could a group of UTM's all connected together like a connectionist machine all be organized together so they could 'operate' themselves like one 'group - conglomerate UTM? $\endgroup$ – 201044 Sep 29 '15 at 21:48
  • $\begingroup$ no it can't, a UTM is just one and applies {simulates} itself to be connected according to the input itself. $\endgroup$ – ABD Oct 22 '15 at 20:13
  • $\begingroup$ Could a connectionist machine be considered to be a collection of dynamic subsystems each acting like a turing machine? $\endgroup$ – 201044 Nov 5 '15 at 20:19
  • $\begingroup$ Yes it can be considered as a collection of turing machine BUT we should also keep in mind that this collection of turing machines can be simulated by a single turing machine, so the connectionist machine is not something that can do more than what a single turing machine can do $\endgroup$ – Ankur Nov 6 '15 at 3:46

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