Will encoding affect computability? 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.)