Transposition in Turing Machine

File: 2.png (7KB, 810x245px) Image search: [Google]

7KB, 810x245px

This must be the result. It must work for any amount of 1s

>>230542
Repost from /sci/:

Is it a 1 tape turing machine? Must it be deterministic? What alphabet is it using?

>>230585
Yes, there's just a one tape and it must be deterministic for ANY amount of 1s in right and left. It must start from space in between them and it must end there too. I think, it may use any alphabet.
I shouldn't have created thread in /sci/, because that's not the right board for this

>>230597
Write a placeholder symbol at each end, and move each placeholder inwards one symbol at a time, writing the symbol from the other end in the place where it was. When you have two placeholders next to one another, move right to the end of the tape moving every symbol left one, then seek back left to the placeholder, remember the symbol to the left of it, move every symbol apart from the one to the left of the placeholder left one, seek right to the placeholder and replace it with the symbol you remembered.

It's a lot of states and a lot of corner cases, but it's deterministic and requires no extra tape and only one extra symbol.

File: 3.png (10KB, 1151x245px) Image search: [Google]

10KB, 1151x245px

>>230635
>move right to the end of the tape
You mean that 3rd cell, right? What should I do next?
>moving every symbol left one
do you mean I should look for remaining 1s or what? How the program would know how many 1s it needs to set?
I may upload the program, if you want

>how to make an algorithm
By defining it in some language

>>230652
>>230652
>>230652
>You mean that 3rd cell, right?
I guess. Why are you testing it on a tape that doesn't contain a valid input?

>>230652
>>moving every symbol left one
- move right 2
- if (1), move left 1, write (1); if ( ), move left 1, write ( ); if (EOT), done
- repeat if not done

>>230654
Too hard.
>Why are you testing it on a tape that doesn't contain a valid input?
Because it should be in this TM emulator.
Here's the link if you still want to try to help me: https://drive.google.com/file/d/0B2plXkllyW8SU0JpYXlqcVVvT28/view?usp=sharing
I'll be afk for 30 minutes

Is anyone still here?

File: SUCCESS.png (11KB, 1138x248px) Image search: [Google]

11KB, 1138x248px

I just came up with an idea (is it the right construction of sentence it english?) and got this "puzzle" solved. Thank you for trying to help me.