People who code: we want your input. Take the Survey

New answers tagged

-3

The standard pseudo-code halting problem template "proves" that the halting problem could never be solved on the basis that neither value of true (halting) nor false (not halting) could be correctly returned to the confounding input. This problem is overcome on the basis that the halt decider aborts its simulation of this input before ever ...


5

Here are some natural problems which are complete for $\Sigma^0_3$: Given $\langle M \rangle$, is $L(M)$ cofinite? Given $\langle M \rangle$, is $L(M)$ recursive? Given $\langle M \rangle$, is $L(M)$ regular? Given $\langle M \rangle$, is $L(M)$ context-free? In all of these, $L(M)$ is the set of inputs on which $M$ halts. See these lecture notes.


4

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 ...


0

Ĥ.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 ...


2

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 ...


-2

The following concrete example shows that the confounding input is aborted before it ever receives any return value from the halt decider. The simulating halt decider H aborts its input because this input specifies infinite invocations comparable to infinite recursion. When a simulating halt decider must abort the simulation of its input to prevent the ...


0

You are confusing the langauges here $h(\langle M, w, \varepsilon\rangle) \notin L$ certainly, but this does not mean anything releated to $L_{halt}$. Assume $M$ halts on $w$ after $i$ moves. Then $\langle M, w, c^i \rangle \in L$ and $\langle M, w\rangle \in L_{halt}$. Moreover, $h(\langle M, w, c^i \rangle) = \langle M, w \rangle$. Otherwise assume $M$ ...


1

The gist of the argument is that the assumption that a one can write a function halt(f) that always halts and always answers correctly if f halts leads to a contradiction (by way of self-reference, applying it to a variant of itself), thus such function can't be written. Sure, you can write functions that answer "Yes", "No", or "Don'...


1

The idea is to determine how many of the Turing machines halt. We will show more generally that given $N = 2^n-1$ many Turing machines $T_1,\ldots,T_N$, we can determine which of them halt (on the empty input) using only $n$ calls to an oracle that solves the halting problem. First, let us see how to determine, using a single oracle call, whether at least $\...


Top 50 recent answers are included