I am wondering why the computable function is defined in the natural number set. Can people give me the answer or some resources that can solve my puzzle.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I think this question would be better at math.stackexchange, and with more context. $\endgroup$– Noah SchweberCommented Nov 29, 2016 at 3:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The natural numbers are often used as a background for (ordinary) computability theory because they are a simple and widely known system of finitary objects. Alternative possibilities would be finite strings of symbols from a fixed finite alphabet (which were, if I remember correctly, used as the background in Shoenfield's book "Recursion Theory") or hereditarily finite sets. The particular choice of background makes little difference, as any reasonable finitary background can be computably coded in any other.
answered Nov 29, 2016 at 3:27
-
$\begingroup$ To play devil's advocate, your conclusion "The particular choice of background makes little difference, as any reasonable finitary background can be computably coded in any other." is precisely the content of the question, and I don't believe that your argument proves this.. What does "reasonable finitary background" mean here? This is far from obvious. For example is it obvious that the smn theorem is preserved under any "reasonable" map between any two "finitary backgrounds"? $\endgroup$ Commented Nov 29, 2016 at 7:52
-
1$\begingroup$ @SJR My answer certainly doesn't prove anything; none of it is intended as a proof. For a careful treatment of some issues involved in the coding aspect of computability theory, you might look into the work of Nachum Dershowitz and Udi Boker, for example their paper "Comparing computational power". $\endgroup$ Commented Nov 29, 2016 at 16:46