-5
$\begingroup$

When we hypothesize that the halt decider embedded in Ĥ is simply a Universal Turing Machine (UTM) does this define a computation that never halts when Ĥ is applied to its own Turing machine description?

The purpose of this hypothetical question is to create the basis for a follow-on question. It is obvious that UTM is not a halt decider and would itself never halt when applied to inputs that never halt.

The following simplifies the syntax for the definition of the Linz Turing machine Ĥ, it is now a single machine with a single start state. The halt decider is embedded at state Ĥ.qx.

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt


Figure 12.3 Turing Machine Ĥ

enter image description here

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Discrete lizard
    Jul 11 at 18:14
5
$\begingroup$

This is an answer to an attempt at understanding a previous version of the question, and is no longer relevant to the latest question.


Your question is: What happens when you use a simulating halt decider and (...)?

The answer is: You can't. The question has a faulty premise. A simulating halt decider does not exist, so there is no meaningful answer to the question.


I'll highlight your definition. You propose the following definition:

A simulating (at least partial) halt decider H is a UTM that has been adapted to decide whether or not its input halts. It does this by simulating its input and examining the behavior of this simulated input.

(I presume this should be interpreted as saying that, to count as a simulating halt decider, the UTM must always correctly decide whether or not its input halts, for all possible inputs.)

The problem is: there does not exist any UTM that successfully acts as a simulating halt decider on all inputs.

You can add all the conditions and requirements you want to a definition. The definition remains valid. But there is no guarantee that there exists any object that meets the conditions of the definition. That has to be separately verified.

It sounds like you think that there does exist such a UTM that would qualify as a simulating halt decider. However, your intuition is faulty. I know it's easy to identify some patterns that, if they arise during execution, allow us to determine whether the input will halt. However, those patterns will never be comprehensive. No matter how many patterns you write down, there will always be some inputs that aren't handled by any of those patterns.

Those of us who have studied complexity theory already know this, because there is a theorem that proves it. High-level statements such as "Certain patterns of behavior such as infinite loops and infinite recursion can be recognized." is not likely to be effective at persuading anyone to the contrary, because we know there are also other kinds of behavior that won't be recognized; yet such language is too vague and imprecise to allow us to give you specific examples to help you see that fact concretely.


If you'd like to pump your intuition, you can find some examples of programs where no one knows whether they halt or not: What are the simplest examples of programs that we do not know whether they terminate?, What are very short programs with unknown halting status?. If you study them, perhaps it will give you a better sense why these programs might fail to halt (they might run forever) without ever entering any loop, or even matching "pattern" that you can write down. (More specifically, for any pattern or list of patterns you have in mind, there might be some input that fails to halt but doesn't match any of those patterns.)


If you want an analogy, I find your assertions to come off (to me) as similar to the following made-up conversation:

Polly: Let's define an "awesome circle" to be a circle whose radius $r$ and circumference $C$ satisfy the relationship $C=8r+1$. What would happen if we replaced the 4 tires on my car with objects that have an "awesome circle" shape?

Conan: You can't. No such object exists. The question is meaningless.

Polly: Sure, but assume $H$ is an awesome circle, and I put it on my car. What happens?

Conan: You can't. $H$ doesn't exist. The assumption is false.

Polly: But my $H$ is defined to be awesome. An awesome circle is one that has been adapted so that $C=8r+1$.

Conan: You can't. You can't adapt a circle that way.

Polly: I have superior knowledge of round shapes. Anyone with my experience with round shapes would see immediately how to adapt a circle in that way.

I hope you can see how this exchange is a bit absurd and Conan would tire of it quickly and not have any interest in continuing the conversation. Of course, if Conan knows some mathematics, then he immediately knows that all circles satisfy the relationship $C=2\pi r$; since there is no solution to the system of equations $C=2 \pi r$, $C=8r+1$ with $r \ge 0$, any mathematician would immediately know that no "awesome circle" can exist, so there is not much point in continuing such a conversation.

This is how your attempts to address this topic come off to me. Your assertions remind me of Polly's assertions (Polly's awesome circle = your simulating halt decider; Conan = any computer scientist who has studied decidability). Hopefully this helps you better understand the reactions you are getting and use it to help you focus your future studies.

$\endgroup$
6
  • $\begingroup$ "(I presume this should be interpreted as saying that, to count as a simulating halt decider, the UTM must always correctly decide whether or not its input halts, for all possible inputs)." I already stipulated that this assumption is incorrect when I said "at least partial halt decider". My goal is limited to refuted the conventional proofs. My goal is not to prove that halting is decidable. A partial halt decider exists even if it only decides one input. $\endgroup$
    – polcott
    Jun 9 at 21:14
  • $\begingroup$ @polcott, OK. That wasn't clear to me. If that's what you mean, then the question isn't answerable in its current form. You ask what is the behavior of <<something with $H$>> but you haven't specified $H$. You listed some conditions you want us to assume $H$ satisfies, but you haven't identified a single TM $H$. There remain many possibilities for what $H$ could be. So, there's not enough information to answer the question; the behavior will likely depend on which specific $H$ we are looking at. $\endgroup$
    – D.W.
    Jun 9 at 21:18
  • $\begingroup$ Also, it's not clear what kind of an answer you'd be looking for, when you ask "What is the behavior". Do you want an execution trace? An English description of what it does? If so, what do you want to be in that English description? $\endgroup$
    – D.W.
    Jun 9 at 21:19
  • $\begingroup$ I am saying that under the conditions that I specify when Ĥ is applied to its own Turing machine description I see an infinitely repeating that never halts unless the simulation is aborted. Do you see this same infinitely repeating pattern? That is the essence of my whole question. $\endgroup$
    – polcott
    Jun 9 at 21:23
  • $\begingroup$ @polcott, I don't see that asked in the question. It's hard to answer questions if I have to guess what is being asked. $\endgroup$
    – D.W.
    Jun 9 at 21:29
2
$\begingroup$

In response to an earlier version:

You have misunderstood their proof, which is not very well presented (imho); but you also seem to have cut off the end, where they establish the contradiction.

They do not state anywhere that $M$ is simulated, at all.

$\hat H$ simulates $H'$ and $H'$ simulates $H$. Now, $H$ is assumed -- towards a contradiction -- to be decider. which means it always terminates after finitely many steps. No assumption is made on how it solves the halting problem -- which is the point, of course, because only so can be disprove all candidates for $H$ by leading the assumption to a contradiction!

So we simulate $H$ which always terminates -- no infinitely nested simulation is happening.

Your intuition is not wrong, though, even though you seem to be missing the corner cases: you'd need something like "infinitely nested simulation" to solve the halting problem -- something that doesn't work. Because it's impossible.


When we hypothesize that the halt decider embedded in Ĥ is simply a Universal Turing Machine (UTM) does this define a computation that never halts when Ĥ is applied to its own Turing machine description?

There are infinitely many UTMs. Without further assumptions, we just don't know what any arbitrary one of those does on its own encoding.

$\endgroup$
14
  • 1
    $\begingroup$ @polcott You don't get to make assumptions on how H works. $\endgroup$
    – Raphael
    Jun 8 at 0:01
  • 1
    $\begingroup$ No: cs.stackexchange.com/questions/141080/… Hard as it is, at some point you'll have to reconsider the idea that you acually haven't understood the proof. $\endgroup$
    – Raphael
    Jun 8 at 8:35
  • 2
    $\begingroup$ There is no material here to spend more time on. I'm sorry you wasted all that time. $\endgroup$
    – Raphael
    Jun 8 at 13:56
  • 1
    $\begingroup$ By the way: even if you managed to come up with some machine that can solve its own halting problem, that does not solve the halting problem. $\endgroup$
    – Raphael
    Jun 8 at 13:57
  • 3
    $\begingroup$ @polcott Does this help? cs.stackexchange.com/a/112230/1329 $\endgroup$ Jun 9 at 7:17
-2
$\begingroup$

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qy ∞
if M applied to wM halts, and

Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
if M applied to wM does not halt


Figure 12.3 Turing Machine Ĥ

Ĥ.q0 copies its input then Ĥ.qx simulates this input with the copy then
Ĥ.q0 copies its input then Ĥ.qx simulates this input with the copy then
Ĥ.q0 copies its input then Ĥ.qx simulates this input with the copy then...
This is expressed in figure 12.4 as a cycle from qx to q0 to qx.


Figure 12.4 Turing Machine Ĥ

Within the hypothesis that the internal halt decider embedded within Ĥ simulates its input Ĥ applied to its own Turing machine description ŵ seems to derive infinitely nested simulation, unless this simulation is aborted.

Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (318-320)

$\endgroup$
1
  • $\begingroup$ This only proves that it is impossible for a halt decider to be simulating for all inputs. $\endgroup$
    – user253751
    Sep 20 at 8:16

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.