given the following languages:

  • $INFINITE_{T M}=\{\langle M\rangle: M$ is a TM with $|L(M)|=\infty\}$.
  • $R E G_{T M}=\{\langle M\rangle: M$ is a TM with $L(M) \in \mathrm{REG}\}$.

prove the following reduction:

$I N F I N I T E_{T M} \leq_m R E G_{T M}$ I'm having difficulties, building the $M_f$ machine

would love for some help, got no clue for now :)

edit: if that wasn't clear, would love for initial direction, not for formal solution

  • $\begingroup$ We're not looking for posts that are just the statement of an exercise-style task and a request for us to solve it for you. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. Can you ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the same problem you happen to be working on. $\endgroup$
    – D.W.
    Jun 4, 2023 at 18:17
  • $\begingroup$ Please edit your question to define REG. $\endgroup$
    – D.W.
    Jun 4, 2023 at 18:26
  • $\begingroup$ I don't get why you should be so toxic, and adding -1 to the post, I'm not here for you to solve my exercises, I'm here to learn, and when I state i don't have any clue, I mean it, I've tried to solve this questions for like couple of days, and still don't have any clue how to begin, yes I know what is reduction and I know that it's needs to get machines that in one language and output machine that from the other language, would love for some help, thank you $\endgroup$ Jun 4, 2023 at 19:00
  • $\begingroup$ ah and another thing , this attitude is the reason I considering not to continue taking part in this community, I know there are many that will continue participate here, but if you are looking to expand the community find a better way to answer frustrated students , who has no clue how to proceed in this question, and no , I didn't ask for a formal answer, a beginning of direction to solution would be nice $\endgroup$ Jun 4, 2023 at 19:09
  • $\begingroup$ E.g. let $M_f$ accept any non-regular language like $\{a^{p_n}| n \in \mathbb N\}$ $p_n$ primes, and only fill in all the remaining $a^i$ if $M$ accepts infinitely many words. Note that checking if a word exists such that a TM accepts a word longer than $i$ is in RE. $\endgroup$
    – plshelp
    Jun 4, 2023 at 19:45

1 Answer 1


The following reduction mapping should work. For any input $M\in TM$ we define $M_f$ as follows: For any $x\in\Sigma^*$,

  1. If $x=0^n1^n$ for any $n\in \mathbb{N}$ then $M_f$ Accepts.
  2. Else, we run simultaneously $M$ on all words $y\in\Sigma^*$ in Minlex order such that $|y|\geq|x|$. If $M$ Accepts, then $M_f$ Accepts.
  3. If no word was Accepted, we continue running.

It isn't difficult to see that $M_f$ is computable, and now I will leave you to prove that it is indeed a correct reduction.

  • 1
    $\begingroup$ Yup done something like this , a couple of days ago :) thank you very much! you are the best $\endgroup$ Jun 7, 2023 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.