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?
Will encoding affect computability?
computability;undecidability;decision problem