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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Definition
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
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.
 
Evgeny.Makarov said:
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?
 
evinda said:
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$.
 
Evgeny.Makarov said:
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?
 
evinda said:
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.
 
Evgeny.Makarov said:
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?
 
evinda said:
If $n \in L$
You should have written this from the start. I agree with the rest of your last post.
 
Evgeny.Makarov said:
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?
 
  • #10
evinda said:
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$.
 
  • #11
Evgeny.Makarov said:
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?
 
  • #12
evinda said:
We want to reduct
Reduce.

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

evinda said:
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.
 
  • #13
Evgeny.Makarov said:
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)
 
Back
Top