Meaning of Definition: $T_n(1)$ Defines a Function

[evinda]

Hello! (Wave)

I want to show that the language $L=\{ n \in \mathbb{N}_0 \mid T_n(1) \text{ defines a totally defined function }\}$ is not decidable.

What does it mean that $T_n(1)$ defines a totally defined function?

Does it mean that $T_n(x)$ is a totally defined function and $1$ belongs to the domain? (Thinking)

 

[Evgeny.Makarov]

Yes, this seems like a typo. Perhaps it should read "$T_n(x)$ defines a totally defined function". If the function computed by the machine with code $n$ is indeed total, then 1 belongs to the domain by definition.

 

[evinda]

Yes, this seems like a typo. Perhaps it should read "$T_n(x)$ defines a totally defined function". If the function computed by the machine with code $n$ is indeed total, then 1 belongs to the domain by definition.

So we know that $T_n$ is defined for all $x$. And there are two possible cases:

• either $T_n(x) \uparrow$
• or $T_n(x) \downarrow$

So do we use the fact that the languages $\{ n \in \mathbb{N} \mid T_n(x) \downarrow \}$, $\{ n \in \mathbb{N} \mid T_n(x) \uparrow\}$ are not decidable?

 

[Evgeny.Makarov]

So we know that $T_n$ is defined for all $x$.

I am not sure where this follows from or where it was assumed and for which $n$.

 

[evinda]

I am not sure where this follows from or where it was assumed and for which $n$.

I thought that it would follow from this: "$T_n(x)$ defines a totally defined function". What is it then mean?

 

[Evgeny.Makarov]

I thought that it would follow from this: "$T_n(x)$ defines a totally defined function".

But where does this follow from or when was this assumed? Until you say what $n$ is, it makes no sense to discuss this statement.

 

[evinda]

But where does this follow from or when was this assumed? Until you say what $n$ is, it makes no sense to discuss this statement.

If $n \in L$, then we have that $T_n(x)$ defines a totally defined function. And this means that $T_n$ is defined for any input. Right?

 

[Evgeny.Makarov]

If $n \in L$

You should have written this from the start. I agree with the rest of your last post.

 

[evinda]

You should have written this from the start. I agree with the rest of your last post.

And so if $n \in L$ does it mean that $T_n(x)$ always halts?

 

[Evgeny.Makarov]

And so if $n \in L$ does it mean that $T_n(x)$ always halts?

Yes.

You should probably reduce an undecidable language to $L$. Consider reducing $Halt$.

 

[evinda]

Yes.

You should probably reduce an undecidable language to $L$. Consider reducing $Halt$.

So, let $n \in L$. Then we have that $T_n(x) \downarrow$ for any input $x$.

We want to reduct $H=\{ n \in \mathbb{N}\mid T_n(n) \downarrow \}$ to $L$.

Given $n$, we construct a Turing machine $M$ that erases its input, writes $n$ and then behaves as $T_n$.

Thus $M$ on any input ( including $x$ ) simulates $T_n(n)$ and thus we deduce that $L$ is undecidable.

Right?

 

[Evgeny.Makarov]

We want to reduct

Reduce.

Given $n$, we construct a Turing machine $M$ that erases its input, writes $n$ and then behaves as $T_n$.

Yes.

Thus $M$ on any input ( including $x$ )

Don't use entities that were not properly introduced. In programming way of speaking, variable $x$ is undefined.

 

[evinda]

Don't use entities that were not properly introduced. In programming way of speaking, variable $x$ is undefined.

Oh yes. We have that $x$ could be any string.

Thanks a lot! (Smile)