Turing machine

[SabrinaAlex]

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.

Regards

Sabrina

[apines]

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.

[SabrinaAlex]

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

Sabrina

[apines]

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.

[SabrinaAlex]

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

[SabrinaAlex]

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

[apines]

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

[SabrinaAlex]

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

[paoconnell]

Go to this Wikipedia page
http://en.wikipedia.org/wiki/Turing_machine

[SabrinaAlex]

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

[apines]

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

[happygeek]

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

[paoconnell]

Look here:

http://stackoverflow.com/questions/236000/whats-a-turing-machine

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.