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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Dec 25, 2015 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
    Commented Dec 25, 2015 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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