I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the encoding may(intuitively) not affect the computability of the problem, Is it true? Can I have a computable problem which on changing the encoding turns uncomputable?For eg given a graph and two vertices, the problem is whether there is path between them. We know this is compuatable. But if we consider encoding as just a mapping, then If I have encoding such that set of all instance of the problem with the answer as yes mapped to some undecidable language(bijectively)?Is it possible?
As long as there's a computable mapping between the two encodings, changing from one to the other won't affect computability, since computable functions compose. If there isn't a computable mapping between the encodings, you can't effectively use at least one of them, since there's no way to figure out what the encoding of your input should be in that scheme. (For example, suppose you come up with a coding of graphs that isn't computably translatable from the adjacency matrix. How would you use that encoding? If I give you a graph, you can't figure out what string encodes it.)
A TM is not the sole means of implementing an 'Effective procedure' while the ones it does carry out are constrained to accept input only as strings of symbols over some finite alphabet.
But it is widely believed that every effectively calculable function...i.e one calculated through an effective procedure can also be carried out through a TM.(Church -Turing thesis)
In view of above the entire process of assigning a unique string to an object of input space...and its further manipulation to reach a decision...is one single 'effective procedure'...if at all one exists:part of which is carried out by a TM.
And if the problem is not decidable then no such procedure exists.
Hence the decidability status of the problem is inherent to the problem itself...
And if an effective procedure does produce a string having one to one correspondence with the problem...then a TM can decide it (if the problem is decidable through an effective procedure)...irrespective of the encoding.