I'm reading about Computability and so far I have found it a bit difficult to understand, given that I have a narrow mathematical background, and that often times I would find different names for the same thing, or different definitions for one concept (as in the case of an algorithm)
I have the following statements/questions that I would like to be corrected/answered:
- we define recursive and primitive recursive functions on N^k -> N^k (because then we can utilize the proof by induction to show that all iterations of said function are recursive/primitive recursive functions).
- the set of all total functions is included in the set of all partial functions.
- a primitive recursive function must always be a total function, otherwise it wouldn't be primitive recursive.
- a recursive function is always a partial function.
- every recursive function is calculable (representable by an algorithm (set of instructions) that halts eventually, i.e. returns a value eventually for every input.
- if a recursive function is a partial function (can be defined on only a portion of N^k), doesn't that mean that it isn't calculable outside of that portion of N^k, thus not calculable? (since the function wouldn't return a value for input outside of its definition domain).
- a set is recursively enumerable if and only if it is characterized by a calculable function, meaning a function that halts eventually. (I'm asking this because Wikipedia says that an enumerable set can be characterized by an algorithm that runs forever, but that doesn't make sense to me since that wouldn't be calculable (wouldn't terminate)).
- why must primitive functions be total? if a recursive function can be partial and not total and still calculable, can't a primitive function also be defined on a subset of N^k and still be primitive recursive?
- why are primitive recursive functions called primitive? (is it because an algorithm that calculates them would be simple i.e. primitive? (using just a bunch of for loops)).
- "recursive function" is synonymous with both "general recursive function" and "partial recursive function".
if a recursive function is a partial function (can be defined on only a portion of N^k), doesn't that mean that it isn't calculable outside of that portion of N^k, thus not calculable? (since the function wouldn't return a value for input outside of its definition domain).
There are partial recursive functions such as the empty function (with domain equal to the empty set).
I guess you mean primitive recursive functions. They are total by definition (using the five scheme).