Help with proving a language is in R , RE\R or outside RE

[GoatHunter]

Hi, I'm having trouble with reductions and classifying the following language:
L ={ <M> ∀w∈Σ* Tm(|w|) = c }

That is, L is a language of turing machine encodings such that for any input w
the runtime of the machine is a constant c.

The goal is to classify the language - whether its in R, RE\R or outside of RE.

Proof needs to be shown via reduction or usage of the Rice theorem.

If anyone would at least give me a direction to start with it'll be great.

On one hand it would seem it belongs to RE since its blocked by a constant, on the other hand all input is required to be blocked by the running time of c.

Thanks beforehand, GoatHunter.

[Rashakil Fol]

A great first post!

The key here is to notice that during the first C timesteps, a Turing machine's behavior can only be affected by the first C elements of input.

[GoatHunter]

A great first post!

The key here is to notice that during the first C timesteps, a Turing machine's behavior can only be affected by the first C elements of input.

Hi, the constant C blocks the runtime from above asymptotically, its not the amount of input passed into the machine.
The input size is denoted by |w|. The trouble is that each machine in the language has to have the same maximum running time for any input which consist of the regular expression: [01]*.

My guess is that its not in RE\R nor in R, since how can you run a machine on all possible inputs when inputs are infinite and check whether on all those inputs the machine stopped after time C.

What do you think?

Thanks again.

[Rashakil Fol]

You didn't understand what I was saying. Read it again.

[GoatHunter]

You didn't understand what I was saying. Read it again.

Hi, I'm afraid I need some clarification regarding what you meant and how can this help me classify the language, my main issue is be sure which language class to reduce from.

Thanks beforehand.

[Rashakil Fol]

My guess is that its not in RE\R nor in R, since how can you run a machine on all possible inputs when inputs are infinite

My point is that the relevant part of the inputs are not infinite.

[GoatHunter]

My point is that the relevant part of the inputs are not infinite.

Hi, could you walk with me through solving this problem, I could really use some help as I'm lost in the area of reductions and language classifications.

[Rashakil Fol]

> Hi, could you walk with me through solving this problem

No, there are more important things than solving this problem. Your ability to think clearly is at stake.

> On one hand it would seem it belongs to RE since its blocked by a constant, on the other hand all input is required to be blocked by the running time of c.

I don't know how to parse this statement. What does "blocked by a constant" mean? It's an ambiguous thing to say and you should be saying things unambiguously.

> My guess is that its not in RE\R nor in R, since how can you run a machine on all possible inputs when inputs are infinite and check whether on all those inputs the machine stopped after time C.

Here, you're saying wrong things. Inputs are not infinite, because, with Turing machines, inputs are finite. The set of inputs is (countably) infinite. Why are you saying "inputs" when you should be saying "set of inputs"? You're casually mixing up the two terms. I don't know why you're doing this. Either you don't understand the distinction between having a given type of thing versus having a set whose elements are a given type of thing (which seems improbable), or you don't feel like holding thoughts in your mind correctly or writing them correctly. The same goes for your "blocked by a constant" statement. It takes effort to be rigorous and clear, when you have other things in your mind, and you only have a finite amount of volatile short-term memory, but you have to do it.

> I could really use some help as I'm lost in the area of reductions and language classifications.

An important first step is to double-check your intuition by reiterating your intuitive thoughts using rigorous reasoning, and by questioning your assumptions. For example, the question "since how can you run a machine on all possible inputs when [the set of] inputs [is] infinite" assumes that you would need to run a machine on all possible inputs. What makes you think this assumption is correct?

[GoatHunter]

> Hi, could you walk with me through solving this problem

No, there are more important things than solving this problem. Your ability to think clearly is at stake.

> On one hand it would seem it belongs to RE since its blocked by a constant, on the other hand all input is required to be blocked by the running time of c.

I don't know how to parse this statement. What does "blocked by a constant" mean? It's an ambiguous thing to say and you should be saying things unambiguously.

> My guess is that its not in RE\R nor in R, since how can you run a machine on all possible inputs when inputs are infinite and check whether on all those inputs the machine stopped after time C.

Here, you're saying wrong things. Inputs are not infinite, because, with Turing machines, inputs are finite. The set of inputs is (countably) infinite. Why are you saying "inputs" when you should be saying "set of inputs"? You're casually mixing up the two terms. I don't know why you're doing this. Either you don't understand the distinction between having a given type of thing versus having a set whose elements are a given type of thing (which seems improbable), or you don't feel like holding thoughts in your mind correctly or writing them correctly. The same goes for your "blocked by a constant" statement. It takes effort to be rigorous and clear, when you have other things in your mind, and you only have a finite amount of volatile short-term memory, but you have to do it.

> I could really use some help as I'm lost in the area of reductions and language classifications.

An important first step is to double-check your intuition by reiterating your intuitive thoughts using rigorous reasoning, and by questioning your assumptions. For example, the question "since how can you run a machine on all possible inputs when [the set of] inputs [is] infinite" assumes that you would need to run a machine on all possible inputs. What makes you think this assumption is correct?

By saying "blocked by a constant" I meant upper bound, then if C is the running time of a TM in that language the worst case size of an input string will be C which means the length of input strings coming from the set Sigma* if finite and thus their power is finite.

Hmm,
So build a turing machine M' which runs the given turing machine on set of all inputs in which each item is at most size C and make sure it makes at most C steps.
If that machine M accepts then M' accepts if M rejects then M' rejects.

Hence it's in R.

What do you think?

[Rashakil Fol]

You shouldn't need to ask other people if a proof is incorrect if you understand how logic works.