3 \langle, \rangle

Let $$L_{NTF} = \{ \langle M \rangle \mid$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$$$\langle M\rangle$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$$$\langle M\rangle$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

Let $$L_{NTF} = \{ \langle M \rangle \mid$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

Let $$L_{NTF} = \{ \langle M \rangle \mid$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$\langle M\rangle$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$\langle M\rangle$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

2 added 17 characters in body; edited tags; edited title

# Is this languagethe set of TMs that does not reach most cells to the right computable?

Let $$L_{NTF} = \{ |$$$$L_{NTF} = \{ \langle M \rangle \mid$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

# Is this language computable?

Let $$L_{NTF} = \{ |$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

# Is the set of TMs that does not reach most cells to the right computable?

Let $$L_{NTF} = \{ \langle M \rangle \mid$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...

1

# Is this language computable?

Let $$L_{NTF} = \{ |$$ for every $$x\in\Sigma^*$$ the machine $$M$$ does not reach the $$|x|+10$$'th cell during its calculation on $$x$$. $$\}$$.

I would like to prove or disprove $$L_{NTF} \in RE$$.

I know how to easily prove that $$L_{NTF} \in Co$$-$$RE$$, because it is enough to find one word $$x$$ such that $$M$$ will reach the $$|x|+10$$'th cell during its calculation on $$x$$. There is a finite number of configurations as long as the machine does not reach the $$|x|+10$$'th cell, so if I see a configuration is repeated I can deduce that the calculation will not end, but since I want it not to reach the $$|x|+10$$'th cell it is fine by me. That is to say, for a given input $$x$$ I can decide whether or not it reaches the $$|x|+10$$'th cell during $$M$$'s calculation on $$x$$.

So this tells me that $$\overline{L_{NTF}}\in RE$$, that is $$L_{NTF}\in Co$$-$$RE$$.

But this idea will not assist me in proving $$L_{NTF}\in RE$$ because I may accept a TM $$$$ only after I will iterate over all possible $$x\in \Sigma^*$$, and since $$\Sigma^*$$ is $$\aleph_0$$ I will never accept a TM $$$$. This is my intuition for why $$L_{NTF} \notin RE$$.

So for proving this I have 2 options:

1. Showing a reduction $$L\leq L_{NTF}$$ where $$L\notin RE$$. I've tried using $$\overline{L_{acc}}, L_d$$ and $$L_{\Sigma^*}$$, but could not find such a reduction that will hold. I'm not sure which language should i reduce from?
2. Finding a correspoinding property using Rice's theorem. I believe this idea will not work because the property is on the TM and not on the language.
3. An idea similiar to (1), just showing a reduction $$L\leq L_{NTF}$$ where $$L\notin R$$. This will also be sufficient because it will prove me that $$L_{NTF}\notin R$$, and since I know $$L_{NTF}\in Co$$-$$RE$$ having $$L_{NTF}\in RE$$ will lead to a contradiction, thus we can deduce $$L_{NTF}\notin RE$$.

I believe it is either by option (1) or by option (3), but I could not find a reduction that will prove this...