3
$\begingroup$

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.

This is the problem:

In building an Universal Turing Machine to emulate another Turing Machine, how can we be sure that we are indeed simulating it? ('sure' in the sense of being computationally verified by an algorithm). So I get confused, the problem I found is that Rice's theorem apparently tell us that we can not verify this computationally.. Is not "to emulate" an extensive property?.This lead me to think we could not prove the Universal Turing Machine is doing what it's supposed to do..

EDIT

To expand the topic

I want to expand this point, what I understood from given answers, is you can state that a specific Machine is Universal but not that an arbitrary machine is (nor a family of machines are universal), ok, but I don't ask for arbitrary!, nor a family, but to test algorithmically a single fixed machine. Test, like measuring, is against something, It's hard to think a computer concept without having something to compare with, and according to answers, completeness of a machine seems as something that can't be compared.

How universality is proven? let's say by showing 'look mom I am simulating a TM', so, as she believes TM are universal, then your machine is also universal, but, she can't verify it!, she must believe you because she can't test that single machine you made, not by an algorithm, so that's why I see Rice's theorem rubs against completeness, there is no algorithm to test two fixed machines are doing the same computation.

So what can "universal" mean?, it's seems like saying, your software is doing what you mind, because is written in a Turing Complete language!. 'This is emulating a machine because it can'. I think that's not enough.

Improve this question
$\endgroup$
6
  • $\begingroup$ Despite the halting problem, I know that (a TM which performs) bubble sort halts. How is that? $\endgroup$
    – Karolis Juodelė
    Jun 16, 2014 at 19:17
  • 1
    $\begingroup$ That example makes no sense in terms of the question asked, and misrepresents the halting problem. You can easily write a program, and therefor build a TM to tell you that you your bubble sort halts. You just cant design one which says it does not halt, so saying knowing your bubble sort halts as "Despite the halting problem" is wrong. $\endgroup$
    – lPlant
    Jun 16, 2014 at 19:27
  • 3
    $\begingroup$ I think the point about a bubble sort TM is that we can often construct a TM that can be proved to do some specific task, even if we cannot decide the set of all TMs that have that property. $\endgroup$
    – Patricia Shanahan
    Jun 17, 2014 at 2:14
  • $\begingroup$ rice's thm is indeed quite subtle/nuanced & would like to see a survey of it myself. the boundary between decidable/undecidable can be very complex & many papers study it, it is an active area of research. $\endgroup$
    – vzn
    Jun 17, 2014 at 15:10
  • $\begingroup$ I haven't studied Rice's Theorem much, but I thought that Rice's theorem applies to what you can decide about languages. For example, I would have thought that Rice's Theorem says this is not decidable, $\text{{L : L is the set of all encodings of Universal Turing Machines}}$. But that is different than $\text{{<M>: M is a Universal Turing Machine}}$ which I would not have thought Rice's Theorem applies to, even though intuitively I don't think that language is decidable either. $\endgroup$
    – user16480
    Jun 17, 2014 at 18:14

3 Answers 3

Reset to default
11
$\begingroup$

Your misunderstanding is:

'sure' in the sense of being computationally verified by an algorithm

We are not, and we can not be . The question,

Is this given Turing machine $M$ a universal one?

can not be generally and algorithmically decided for the reasons you state.

However, we can prove for a fixed Turing machine that it is universal -- and that is quite enough.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you expand the difference between "a given Turing Machine M", and "a fixed Turing machine" ? $\endgroup$
    – Hernan_eche
    Jun 17, 2014 at 17:23
  • 1
    $\begingroup$ @Hernan_eche Proving that "a fixed Turing machine" is universal means you need to prove universality of that one machine, using any technique you want. Determining whether "a given Turing machine" is universal means that you need to produce a procedure whose input is a Turing machine and whose output is the correct answer to the question, "Is my input universal?" $\endgroup$
    – David Richerby
    Jun 17, 2014 at 17:32
  • $\begingroup$ All of this means that humans are more powerful than Turing Machines :) $\endgroup$
    – gardenhead
    Jun 17, 2014 at 20:37
  • $\begingroup$ @StephenBly Depends on your measure and perspective. If you are interested to discuss this, drop by next week in Computer Science Chat. $\endgroup$
    – Raphael ♦
    Jun 17, 2014 at 21:29
  • 1
    $\begingroup$ @StephenBly not really, because we can also fool humans with some particular inputs. $\endgroup$
    – Denis
    Jun 17, 2014 at 23:37
5
$\begingroup$

I'm not sure I understand your confusion (feel free to expand, if you are still confused), but there two issues that might give you better intuition:

  1. Given a Specific TM $M$, we can know ``for sure'' what it does for all inputs. This is not "sure" in an algorithmic way, but sure in an absolute (mathematical) way.

    Example: Consider the TM that has one state, which is non-accepting. We know for sure what it does: it does nothing. We can prove it mathematically. Same goes for universal TM: we can prove mathematically, that for any (well-defined) input $M',x$, the output will be exactly $M'(x)$. If this is true in an absolute way, what does it mean to be sure of it by a computationally verified algorithm?

  2. There is a difference between knowing what a specific machine does, and deciding, for any arbitrary machine $M'$, what it does. Rice's theorem talks about family of machines that have the same property, so it fits the latter notion. Similarly, "being sure in an algorithmic way that a universal machine simulates a machine $M$" means that we have some decider TM that decides, for any $M'$, if it is a universal machine or not. This is very different then knowing thath one specific machine is universal.

    Maybe to demonstrate this last issue, note that we know that $$ L_{HP} = \{ \langle M,x\rangle \mid M \text{ is a TM that halts on }x\}$$ is undecidable. But for a given specific $M'$ and input $x$, the language $$ L_{HP-M'-x} = \begin{cases}1 & \text{if $M'$ halts on $x$} \\0& \text{otherwise}\end{cases}$$ is very much decidable! (even if we don't know which specific machine decides it :)

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Given the question, it would help to add an explanation of how one would prove that some fixed machine really is a universal Turing machine. That is, you'd prove that it operates by correctly simulating a single step of the machine, and then starts to simulate the next step, and so on. $\endgroup$
    – David Richerby
    Jun 17, 2014 at 17:34
  • $\begingroup$ I would be really interested in an outline of the proof of this or a link. I know that you cannot simply simulate $M'$ on $x$, and accept if $M'$ accepts, reject if $M'$ rejects, for the same reason you cannot decide $A_tm$. My intuition tells me that then the first language is not decidable even though the second is, because finding an algorithm to decide the second one is not always possible. But apparently you can prove, in the absence of knowing the algorithm, that it can be done. Still $A_{tm}$ is not decidable because you need to actually find that algorithm for each $<m,x>$? $\endgroup$
    – user16480
    Jun 17, 2014 at 19:07
  • $\begingroup$ @DavidRicherby this is almost always the case when proving something about the language of a machine: You start with the initial state and continue by induction. Indeed this is an interesting topic, it probably deserves its own thread. $\endgroup$
    – Ran G.
    Jun 17, 2014 at 19:44
  • $\begingroup$ @RanG. Feel free to write a question on the subject and self-answer it! :-) $\endgroup$
    – David Richerby
    Jun 17, 2014 at 19:45
1
$\begingroup$

I think you are stumbling on the building of an universal Turing machine, that process is (implicitly) a proof that the result is universal, by the way the machine is put together. You probably haven't seen any complete construction of such, only (more or less) handwavy explanations that it can be done. The complete constructions (and their proofs) are long, involved, and terminally boring.

Just as an interpreter for e.g. Python is something magical. Yes, I can explain in rough outline how it works, but for you to get really convinced the python program on your computer does the job you'd have to read the program's source and understand it. You can even write a Python interpreter in Python itself, mimicking the "TM that simulates TMs" above. To find out if some random Python program is in fact a Python interpreter is another kettle of fish altogether.

Improve this answer
$\endgroup$

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.