4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ Encoding is in itself an algorithm and as such by Church Turing thesis implementable by a TM.Hence computability status may not be affected...complexity class may change though. $\endgroup$ – ARi Dec 21 '15 at 12:46
  • 2
    $\begingroup$ If the process encoding(E) is itself an algorithm then the problem itself should be formal (encoded in someway as an in input to E). Isn't it? $\endgroup$ – Saravanan Dec 21 '15 at 12:56
  • $\begingroup$ There is a difference between effectively calculable and computable...while the equivalence is established by church Turing thesis.The encoding process itself may not ingest an input string...but is still equivalent to computation by a Turing machine. $\endgroup$ – ARi Dec 21 '15 at 13:05
  • $\begingroup$ Where I Can read about it? In Micheal Sipser's book there is nothing about it till the topic "Decidability". Does that book containing anything about it? $\endgroup$ – Saravanan Dec 21 '15 at 13:39
  • $\begingroup$ Try Wikipedia..Church -Turing' thesis. I give an answer below. $\endgroup$ – ARi Dec 21 '15 at 15:39
7
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ Just to add as long as the two encodings are done through an 'effective method' they will always have a computable mapping. $\endgroup$ – ARi Dec 21 '15 at 14:42
  • $\begingroup$ So, can I say "a problem(formally a function)" let's say graph-connectedness problem is just an informal association to a language or may be a set of languages(translation can be done between them using computable mapping)? Suppose translation is not compuatable then one of the language is a meaningless association to the problem in some sense? $\endgroup$ – Saravanan Dec 21 '15 at 15:09
  • $\begingroup$ @saravanan Yes. Formally speaking, a problem is just a set of strings, so strictly speaking, you should specify how you're encoding graphs as strings if you want to talk about graph connectivity as a problem. In practical terms, though, as long as you stick to "reasonable" encodings, it doesn't matter which one you use, so people often don't specify. And, yes, if you use an uncomputable encoding, it becomes impossible to associate graphs with the strings your Turing machine is processing. $\endgroup$ – David Richerby Dec 21 '15 at 15:14
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.