1
$\begingroup$

Ceitin's theorem says that if a function $\mathbb R_c \to \mathbb R_c$ is Markov computable, then it is Borel computable (or TTE-computable). I find this theorem on Klaus Weihrauch's Computable Analysis - An Introduction. This seems a really famous and beautiful results, but I cannot find a proof. All references are extremely hard to find by all means. It is such a pity.

Does anyone know where can one find the proof of this amazing result is?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In Weihrauch's book, there are references to proofs; following them, one gets to an easily accessible proof here: Theorem 42 in Spreen, 2001, TCS 262. $\endgroup$ Commented Jan 14, 2024 at 12:22
  • $\begingroup$ Tseytin's original proof is easily accessible here (in Russian). $\endgroup$ Commented Jan 14, 2024 at 12:23
  • $\begingroup$ @Carl-FredrikNybergBrodda Thank you! $\endgroup$ Commented Jan 16, 2024 at 8:00

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.