1
$\begingroup$

Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this machine...

Q1. Is there a not trivial example of a Turing decidable problem which still remains decidable once encoded with a non-Turing computable function?

Q2. Is there a counter example?

$\endgroup$
2
$\begingroup$

Q1. The empty language is decidable however you encode it.

Q2. Represent the natural number $n$ as the encoding of the $n$th Turing machine that halts when started with a blank tape. Under this encoding, any set of natural numbers, except for $0$ and $\mathbb{N}$ is undecidable.

$\endgroup$
2
  • $\begingroup$ Thanks. For Q1 the empty language seems a trivial case as there is no decision to be made at all (as would be the set of all strings) $\endgroup$ – ARi Dec 25 '15 at 5:56
  • $\begingroup$ For Q2, won't finite and cofinite sets still remain decidable? I think some infinite, coinfinite sets remain decidable as well: let $M$ halt on blank tape. Then there exists a inf-coinf. set of naturals that once encoded becomes $ \{ \mathsf{pad}^i(\#M)\ |\ i\in\mathbb{N} \}$ which is decidable, where $\sf pad$ is a padding function. $\endgroup$ – chi Dec 25 '15 at 19:25

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.