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

  • MHB
  • Thread starter evinda
  • Start date
  • Tags
    Definition
In summary, the language $L=\{ n \in \mathbb{N}_0 \mid T_n(1) \text{ defines a totally defined function }\}$ is not decidable.
  • #1
evinda
Gold Member
MHB
3,836
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
  • #2
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.
 
  • #3
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?
 
  • #4
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$.
 
  • #5
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?
 
  • #6
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.
 
  • #7
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?
 
  • #8
evinda said:
If $n \in L$
You should have written this from the start. I agree with the rest of your last post.
 
  • #9
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)
 

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

What does "Meaning of Definition: $T_n(1)$ Defines a Function" mean?

This means that the term $T_n(1)$ is being used to define a function. It may represent an input or output of the function, or it may be used in the definition of the function itself.

How is $T_n(1)$ used to define a function?

$T_n(1)$ can be used as an input to the function, meaning that the function operates on the value of $T_n(1)$. It can also be used in the definition of the function, where the function may be defined in terms of $T_n(1)$ or its properties.

What is the role of $n$ in the definition of the function?

$n$ is a variable that represents the input or inputs to the function. It can also be used in the definition of the function to indicate that the function may vary based on different values of $n$.

How does $T_n(1)$ differ from other notations used to define a function?

$T_n(1)$ is a specific notation that may be used to define a function. Other notations, such as $f(x)$ or $g(t)$, may also be used to define a function. The choice of notation is dependent on the context and the preferences of the person defining the function.

Can $T_n(1)$ be used to define any type of function?

Yes, $T_n(1)$ can be used in the definition of any type of function, whether it is a mathematical function, a computer program, or any other type of function. It is simply a notation that is used to define a function and can be applied in various contexts.

Similar threads

Back
Top