0
$\begingroup$

There is a lot of Turing machine out there. Most of them are purpose-specific.

What make universal Turing machine universal? How do we know or prove if a computer is universal?

Edited: Is programmability of universal Turing machine the key to be universal?

$\endgroup$
3
  • $\begingroup$ It is universal since if you feed it as an input a description of another turing machine $M$, and an arbitrary input string $w$, it will simulate $M$ on $w$ - just as if as you had run $M$ on $w$ yourself. Hence, it is called "universal", since it can do any purpose-specific task that you would be able to do with a different machine. $\endgroup$
    – nir shahar
    Jul 31, 2021 at 23:54
  • $\begingroup$ when people usually say "the Turing machine" or "a Turing machine", do they mean "the Universal Turing machine" or other Turing machines? What are some other Turing machines out there beside the Universal Turing machine? $\endgroup$ Aug 3, 2021 at 9:15
  • $\begingroup$ Any algorithm you can think of can be converted to a unique turing machine. Also, when people say "a turing mcahine" they don't necessarily mean "the universal turing machine". $\endgroup$
    – nir shahar
    Aug 3, 2021 at 11:08

1 Answer 1

4
$\begingroup$

You're confusing a few concepts.

"General-purpose computer" is a high-level, not very well defined term. It's used to refer to computer hardware that is not designed for a specific task and should be able to accommodate most of today's usual (consumer) workloads with reasonable performance and efficiency. Most commercially sold computers and smartphones are considered general-purpose. Examples for non-general purpose hardware would be hardware for database servers or a computer for genome sequencing with additional circuitry or FPGA's.

A universal TM is a TM $A$ whose language is

$$ L(A) = \{\langle M \rangle \# w \mid M \text{ accepts } w \} $$

This is just one of many equivalent ways to give the language. The point is that a universal TM can simulate any provided TM on any provided word.

If you "have" such a turing machine, it would be universal in the sense that you could use it to simulate any other turing machine. There isn't any meaning implied by the word "universal" other than that.

The term "universal computer" isn't used in computer science.

The turing machine is just a model for computability. It can be used to describe the process of computing anything that can be computed (cf. Church-Turing thesis). It's not an ideal model for computing by any other means.

Computer hardware is built to efficiently execute the widest variety of programs and therefore automatically strives to be like a universal turing machine. This, however, isn't really a goal per se. It's just a consequence of the power of the turing machine model.

$\endgroup$
2
  • $\begingroup$ First, thank you for your answer. But I still have some questions. What does "The turing machine is just a model for computability." exactly mean? Does it mean Turing machine can be used to test if a problem is computable? $\endgroup$ Aug 1, 2021 at 19:32
  • $\begingroup$ Yes, that is indeed why Turing invented the TM and this is still its one of its main use in computer science today. The other use is to determine complexity classes, i.e. to determine how hard a problem is in relation to other problems. I really encourage you to look up the Church-Turing thesis, which has held up for almost 90 years and even applies to quantum computing. $\endgroup$
    – idmean
    Aug 1, 2021 at 19:51

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.

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