I tried to do this type of some good random exercise, but I was completely working on it for a month and totally felt unbelievable. I need to see the solution for this type of exercise in order to understand :(. I have hint like 'IF, ELSE, DO' statements, but the solution could help me really to understand completely about Turing Machine.

Consider the alphabets {d, r} Write a Turing Machine
that will recognise the language Stretch(x+1). This is the language of all strings that
contain a continuous string of occurrences of the two letters, followed by ‘*’,
followed by another string of letters with x+1 occurrences of the each letter where
there was a single occurrence in the first string of letters. Here, x = 1. Input to the machine is non-null strings of a, b, *. As an
example, where the letters are ‘a’ and ‘b’ (and x=1) aba*aabbaa, bb*bbbb and
baab*bbaaaabb are in the language, but abb*abbb is not. You may assume that you
have subroutines for writing 0 in the first cell and deleting the rest of the tape and for writing 1 in the first cell and deleting the rest of the tape.

For the mercy, I wish you could help me.

Thank you so much.



If you can build an algorithm for this problem, it means that the problem is computable, therefore it can be done using a Turing machine (Church–Turing thesis). When you look at a string what do you do to determine if it's in the language? Perhaps something of the sort of:

  1. Check the first letter
  2. Go to the * character, and check if the two letters afterwards consists with the first character you have checked
  3. Repeat the steps for all the characters, checking the character before the * and then jumping to the appropriate location after the * (this can be done easily holding some sort of index)
  4. If one of the characters was inconsistent with the language, return false.
  5. if there was no *, return false.
  6. If all letters were consistent and you have reached the end of the string, return true.

An algorithm exists to solve the problem, therefore you can have a Turing machine that will accomplish it.

But I can't visualize in my head to be honest with you :(. I wish you could show me the solution for it and I really want to visualize my head, in the future I will be able to solve others by myself. Please dear, I'm begging that I want to learn more about Turing Machine. Once again, I hope you able to provide the solution above :(.

Best Regards


I gave you the solution - I have showed you an algorithm that solves the problem, therefore invoking the Church Turing thesis it can be done using a Turing machine.

But my dear, I cannot see any codes for turing machine above, when it says write a turing machine, does it mean write in code or as what you've written? I apology for being misunderstanding. Sorry

And one thing dear, as you have provided the solution, what is the code for of that solution?

Showing that an deterministic algorithm exists should suffice as far as I know.

How do you mean? dear if you don't mind explaining to me. Thank you so much for your help.

Wiki is just peaky. I just want the full algorithms for the question above. I wish I could see and learn it in depth.

commented: How about you do your own homework, or at least make a bit of effort, dear -2

You just want someone to do your homework for you. Not going to happen.

In other words you don't want to do any work yourself on this...

Look here:


That gives a good overview. You'll actually need to to study quite a lot more to actually understand who Alan Turing was, why he was important, and why the Turing Machine is important.

Clue regarding Turing machines: all modern computers can be proven to be equivalent to a Turing Machine. Now prove it.