Prove this language is decidable?
To show it's decidable, you just need to give some effective procedure to decide the language. While giving a TM is a pretty straightforward way to do this, it's not the only way. A much easier way to show this language is decidable is to give plain-old pseudocode for an algorithm to decide the language. Consider this:

AcceptsPermutation(
    word : string,
    Accepts : string -&gt; Boolean)
1. permutations = GenerateAllPermutations(word)
2. result = false
3. for each permutation in permutations do
4.     if Accepts(permutation) then result = true
5. return result


In the above pseudocode, Accepts is a function that accepts the target language. Since the target language is decidable, this function is guaranteed to exist; in fact, you have a TM that computes it (or at least, you have something close).

If you can produce pseudocode to generate all permutations of a word, then you're already done. Consider the following:

GenerateAllPermutations(word : string)
1. if length(word) &lt;= 1 then return {word}
2. else then
3.     result = {}
4.     for n = 1 to length(word) do
5.         first = word[n]
6.         rest = GenerateAllPermutations(word[1...n-1] + word[n+1...length(word)])
7.         for each permutation in rest do
8.             result.add(first + permutation)
9.     return result


Apologies if that isn't quite right... with luck, it's enough to convey the idea.

Suppose you really, really want to stick to Turing Machines. We can still make this problem a lot easier by relaxing the restrictions. Consider a multi-tape, multi-TM scenario: one TM reads the input tape, and begins writing permutations to an auxiliary tape. Once a permutation is written, the TM stops, activates a second TM on the new tape, and waits for the answer. If the TM accepts, so do we; otherwise, write the next permutation to the tape. If we run out of permutations to write, reject.

The TM on the second tape is the TM we assume exists since the language $L$ is decidable. All you need now is a $TM$ that can write permutations to a second tape. We might imagine a single-tape TM that works like the above algorithm... it might make the tape look something like this:

Someword_Omeword_Meword_Eword_Word_Ord_Rd_D_
Someword_Omeword_Meword_Eword_Word_Ord_rD_R_
...
someworD_somewoR_somewO_someW_somE_soM_So_O
someworD_somewoR_somewO_someW_somE_soM_sO_S_


Very roughly, the way to get the tapes to look like this is to:


Write out the initial one by capitalizing the first letter, scanning to the end, adding a blank, copy all the lower-case letters between the last two blanks, and repeat until nothing is copied.
Scan to the front; then, scan right, copying each upper-case letter to the second tape as a lower-case letter, until you see two blanks in a row.
Run the second TM on the second tape, to see if that's an accepted permutation.
Clear the second tape.
From the end of the first tape, scan backwards until you see a lower-case letter preceding a blank, erasing anything you see. When you do see a lower-case letter right before a blank, scan left until you see an upper-case letter; change it to lower-case, move right, and change that letter to upper case. Move to the second blank space to the right. Then, proceed to recreate the permutation string as in (1).
Continue in this way until, while scanning left, you see two blanks in a row. This means you've erased the entire tape without finding a matching permutation; since this procedure tries all permutations, you're done.


To make sure you've got it, try to work out the 3rd and 4th permutation strings generated by the above method, as well as the 3rd and 4th from last strings. They should be those given below:

...
Someword_Omeword_Meword_Eword_Word_oRd_Od_D
Someword_Omeword_Meword_Eword_Word_oRd_oD_O
...
someworD_somewoR_somewO_someW_somE_sOm_Sm_M
someworD_somewoR_somewO_someW_somE_sOm_sM_S
...