## Proving undecidability of HALT_tm by reduction

Sipser in his book introduction to the theory of computation provided a proof of undecidability of $$HALT_{TM}$$. He uses a contradiction, he assumed that $$HALT_{TM}$$ is decidable, and built a decider for $$A_{TM}$$, and since $$A_{TM}$$ is already proved by digonalization method to be undecidable, thus the contradiction occurs and $$HALT_{TM}$$ is undecidable. The Turing Machine is simple and straightforward and I’m not going to talk about its details.

What makes me confused is this sentence

We prove the undecidability of $$HALT_{TM}$$ by a reduction from $$A_{TM}$$ to $$HALT_{TM}$$

and I would like to know in which part of the proof reduction actually occurs?

From what we know of the concept of reduction, reducing $$A$$ to $$B$$ means: we have two problems $$A$$ and $$B$$ and we know how to solve $$B$$ but we stuck in $$A$$, then if we reduce $$A$$ to $$B$$, it means solving an instance of $$B$$ will cause solving an instance of $$A$$.

let’s get back to the proof, Sipser says

We prove the undecidability of $$HALT_{TM}$$ by a reduction from $$A_{TM}$$ to $$HALT_{TM}$$

thus $$A = A_{TM}$$ and $$B = HALT_{TM}$$. We don’t know how to solve $$HALT_{TM}$$ and actually this is the problem in hand, furthermore the strategy of the proof is based on contradiction, something that is completely irrelevant to the concept of reduction. Then why Sipser uses the term reduction in this proof?

Posted on Categories proxies

## Undecidability of language involving two TMs

I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.

Given M1, M2 Turing machines, is it true that for every $$x \in \Sigma^*$$ M1 performs at least as many steps while working on input $$x$$ as M2 does with input $$x$$?

There is also an answer to the excercise and a hint, though it didn’t help me that much:

• Let M1 is a TM which enters an infinite cycle for any input → halting problem (and thus undecidable).

• Complement of the language is partially decidable, because non-deterministic TM can provide a counter-example.

In particular, I would like to know how can I express these statements formally:

• How to formally describe the language describing the problem?
• How to reduce the language to halting problem?
• How to show that the complement is partially decidable?

The only thing I can decide with a confidence is that the language itself is not even partially decidable, since complement is partially decidable, but the language itself is not decidable, and thus the language is not even partially decidable (Post theorem).

Posted on Categories proxies

## Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $$M_1$$ and $$M_2$$ behave the same way on an input $$x$$. “Behaving the same way” is defined like this:

$$M_1$$ and $$M_2$$ behave the same way on an input $$x$$, when they both don’t halt, or when they both accept $$x$$ or when they both halt and reject $$x$$.

I found a reduction from the halting problem which uses the fact that if the Turing machines behave in the same way, than they must have the same language. But this all breaks down in the case that $$M_1$$ rejects $$x$$ and $$M_2$$ doesn’t halt, obviously they could have the same language, but they don’t act in the same way.

I do think the best way to approach this is by reducing from the halting problem, but I just can’t find a valid reduction. Any help would be appreciated.

Posted on Categories proxies

## Using undecidability of the halting problem to show that the function also calls recursively in $2i$ if $i$ halts

Let $$\{P_i|i = 1, 2, . . .\}$$ be list of all computable functions. For example, $$P_i$$ might be the $$i$$th program and $$P_i(x)$$ would be the output given by that program on input $$x$$.

Suppose that there is an algorithm to decide whether or not a given procedure calls itself.

Consider the procedure $$FUNC(x)$$:

PROCEDURE FUNC (INTEGER X);       BEGIN INTEGER 1, J;       I ← X DIV 2;       J ← X MOD 2;       IF J = 0 AND Pi(i) halts THEN FUNC (X + l); END 

How do I use Undecidability to show that $$FUNC(2 ∗ i)$$ calls $$FUNC$$ recursively if and only if $$P_i(i)$$ halts?

Posted on Categories proxies

## Can undecidability theorems detected by a machine?

this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question.

This is not a mathematically formalized question. I’m sorry for that but think it’s more like mathematics than philosophy.

When we proved a theorem A which says “B is undecidable”, we don’t try to prove neither B nor (not B). Can a machine do the same thing? Can it detect “meaning” of a statement, like “something is undecidable”?

Here’s a reason why I don’t think so.

Suppose a sentence

universal_Turing_machine(program, input, output) 

is true if and only if resulting output of “program” with given “input” is “output”. Of course, if the program doesn’t halt, it would be false for any “input” and “output”.

Now, let x be a Godel number of a sentence. Consider the following sentence:

there is no y such that: y is a Godel number of a string which ends with a sentence encoded as x,  and universal_Turing_machine(program, y, true) 

If the program acts as a “decision program accepting valid proofs”, this sentence obviously means “a sentence encoded as x is not provable”. If not, this sentence doesn’t mean any undecidability. Hence if a machine can detect undecidability theorems, it has to detect programs which act as “decision programs accepting valid proofs”

But according to Rice’s theorem, detecting programs which has a specific property is not possible.

Do you think this “reason” makes sense? Since this is not a pure mathematical question, I hope to listen to your opinions. Thank you.

Posted on Categories proxies

## Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and machine N. In other words, is language { encodedMachine(M)#encodedMachine(N) | intersection of language of M and language of N is infinite } decidable?

Intuitively it feels like this is undecidable problem and halting reduction might be used to proof this, but I have no idea how to start this reduction.

Posted on Categories proxies

## How is diagonalization a valid argument for the undecidability of the halting problem?

All proofs for the undecidability of the halting problem seem to be based directly or indirectly on self-reference.

def g():     if halts(g):         loop_forever() 

My question is: how can the input of a TM contain the TM itself and its input?

If the description of the TM has states and transitions, then it has more than its input therefore the input of the TM has infinite size because it contains both the TM and the input.

Posted on Categories proxies

## Undecidability of checking whether all words can be generated from a context-free grammar?

I know it’s undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.

Posted on Categories proxies

## Undecidability of emptiness of LBA

How is the emptiness of Linear Bound Automata (LBA) i.e $$L = \{B \mid L(B) = \emptyset \}$$ is undecidable?

Posted on Categories proxies

## Does undecidability violate Turing completeness?

Does undecidability violate Turing completeness?

That is, if one has a language that’s Turing complete, but expresses infinite computation, then why is it meaningful for it to be called “Turing complete”? Wouldn’t it make sense that “Turing complete” is also such that it avoids e.g the halting problem?

Posted on Categories proxies