3
$\begingroup$

I have been quite hesitant to post this question. Due to the highly general nature of the question there is a possibility of a trivial answer. At a first glance at least, one gets the feeling that there should be a trivial negative answer to the questions asked. This has been my feeling for some time at least, without verification. But when actually trying to create a negative example in the last few weeks, I didn't have any luck. But this might not mean much though, partly because I am hardly an expert, and partly because it is just too easy to miss something here that isn't difficult. And hence I thought that it might be better to ask this here. In case there is indeed a (definitive) trivial issue with the question, kindly mention it in comments. If it is quite clear that negative examples are of trivial nature, then I will remove the question.

On the other hand, this also seems to be a fairly natural question to ask (despite the long description). So there is some possibility of a very interesting question (and hence the reason for asking the question).

Firstly a little about the more general context of the question. Suppose we define a collection of "reasonable" functions so that each member of the collection is a function $F:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$. Now, generally speaking, we want to have two desirable properties: (i) The collection of functions shouldn't be too narrow. Narrow meaning that there are obvious functions that should be included in the collection, but aren't. (ii) The collection of functions shouldn't be too wide. Wide meaning that there are functions that we probably don't want to be included in the collection, but they are.

It shouldn't be difficult to think of collections that satisfy property-(i) but fail property-(ii). It also shouldn't be difficult to think of collections that fail property-(i) but satisfy property-(ii). However, satisfying both properties (i) and (ii) simultaneously seems to be difficult (and also connected with other issues). This specific question is about a specific collection of function which I defined sometime ago, which I called "trace-recursive" functions.

The question is divided into three parts. In (1) I just describe the main question directly. In (2) some of the functions that are used in (1) are described. Namely $SeqValue$ and $SeqState$ are described in terms of functions $Value$ and $State$ respectively. In (3) I repeat the notions of address function,representation of a function and notion of step-recursive function (all these notions have been in my previous questions one way or other). But I feel that linking a whole question for just a small description might be a bit strange, so I just describe them here. If there are already standard terms for these notions, then sorry I don't know what they are.

Note that the notions in (2) and (3) are essential to the phrasing of the question. I just separated them to keep the flow of main question more easily tractable.

(1) Main Question: Suppose we are given reasonable model of infinite time calculations. We want to assume both that the running time is transfinite, and also that the range of variables and/or tape length isn't limited to a small value such as $\omega$. So models like ITRM or $\omega$-tape ITTM don't qualify. But it "seems" like a model like ORM (with run-times and variable range restricted to $\omega{_C}{_K}$) will suffice. Similarly it "seems" a model like $\omega{_C}{_K}$-tape ITTM (with run time restricted to $\omega{_C}{_K}$) would also suffice. The usage of phrase "seems" is only because I will admit here that I don't know much about the specific details of these machines/programs at all. I phrased my definition of trace-recursive using "S-while" programs (which I don't describe here because I think the main question remains the same), which coincidentally seem to be sufficient to fully simulate (transfinite) tape for a ITTM in a simple enough manner using a recursion-like command (admittedly naive approach, but it works at least). And the converse of that also seems true. Though I haven't checked all the details to full satisfaction. So it seems like it isn't specifically important what model is used (in the context of this question) as long as there are some basic properties that are satisfied.

Now assume that we fix a very specific reasonable (in the sense described in previous paragraph) computation model $C$. Also suppose (for concreteness) that the model we are considering is program-like so that it uses line numbers and variables/registers. Now assume that there is a single input variable to the program, so that the program can be thought of calculating a function $F:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$. All variables other than input start at values $0$ as per convention. If the length of program is $n$, we number the lines from $0$ to $n-1$ (and $n$ being reserved to describe the "termination line"). The function $State:(\omega{_C}{_K})^2 \rightarrow \mathbb{N}$ has the obvious meaning. $State(t,x)=s$ simply means that when the input given to program is $x$ then at time $t$ the program is at a line number $s$. In a similar manner, we denote the function corresponding to the $i$-th variable as $Value_i:(\omega{_C}{_K})^2 \rightarrow \omega{_C}{_K}$ (with the obvious meaning). $Value_i(t,x)=\alpha$ simply means that when the input given to program is $x$ then at time $t$ the corresponding variable has the value $\alpha$.

Now assume that we have the function $T:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ which describes how long a program runs on a given input (before halting). Now assume that $T$ is total and the following condition holds: $$\sum_{i=0}^{i<\omega{_C}{_K}} T(i) =\omega{_C}{_K}$$ We say that a function $F:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ is trace-recursive iff the function $SeqState$ and the functions $SeqValue_i$(for all variables in the program) are all step-recursive. For a detailed description of "step-recursive" kindly see (3) below. For a detailed description of functions $SeqState$ and $SeqValue_i$ kindly see (2) below.

Here are the questions:

(a) Is the notion of a trace-recursive function fairly robust (with regards to change in computational model) or is it highly sensitive to computational model? Note that for a TM with transfinite time and tape, it shouldn't be difficult to have functions that are analogous to functions $State:(\omega{_C}{_K})^2 \rightarrow \mathbb{N}$ and $Value_i:(\omega{_C}{_K})^2 \rightarrow \omega{_C}{_K}$, which can be quite reasonably be used to describe the trace. It seems to me that the answer should be yes (notion should be robust) but I am repeating this because it is important (and also due to my unfamiliarity with specifics of infinite-models). The next questions only make sense in a fully generic context (that is independently of a specific model) if the answer to this question is positive.

(b) Is there an example of an unnatural trace-recursive function? I don't know of an example, but maybe there is one that isn't hard to find(and show explicitly ofc)? An example would be encoding characteristic function of a non-recursive set below $\omega$ in successor positions (using 0 and 1). Similarly encoding the characteristic function of a non-recursive set on the n-th limit position below $\omega^2$ etc.

(c) Consider two bijective functions $A_1:\alpha \rightarrow \mathbb{N}$ and $A_2:\alpha \rightarrow \mathbb{N}$ ($\alpha<\omega{_C}{_K}$ is some arbitrary value). Now suppose we have a trace-recursive function $F_1$ so that we have: $$F_1(x)=A_1(x) \qquad for \, x<\alpha$$ $$F_1(x)=0 \qquad for \, x \ge \alpha$$ Assume that $F_2$ is also trace-recursive and defined in an identical manner using $A_2$. Define $P:\mathbb{N} \rightarrow \mathbb{N}$ in usual manner as: $$P(A_1(x))=A_2(x) \qquad for \, all \, x<\alpha$$ The question is to give actual examples of two trace-recursive functions $F_1$ and $F_2$ so that $P$ is non-recursive.

If we denote the input variable as the 0-th variable then "maybe" the positions where $SeqValue_0(t)=t$ can be exploited in some way? But perhaps this isn't important and the exploit required is simpler? But I am not clear on this at all either way, so one may take this with a grain of salt.

(2) Defining SeqState and SeqValue: The function $SeqState:\omega{_C}{_K} \rightarrow \mathbb{N}$ is defined from the function $State:(\omega{_C}{_K})^2 \rightarrow \mathbb{N}$ and similarly the function $SeqValue:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ is defined from $Value:(\omega{_C}{_K})^2 \rightarrow \omega{_C}{_K}$. The short description is that $SeqState$ and $SeqValue$ are just nothing more than the "sequential versions" of the functions $State$ and $Value$ in order of increasing input value. That's it as far as informal description is concerend

As an example, assume the $0$-th variable to be the input variable and assume that it is never altered by the program. Whenever we have $SeqState(t)=n$ and $SeqValue_0(t)=\alpha$, then that implies: $SeqState(t+1)=0$, $SeqValue_i(t+1)=0$ (for $i\ne 0$), $SeqValue_0(t+1)=\alpha+1$. Note that the value $0$ indicates the first line and $n$ indicates that program has gone beyond the last line.

To consider this more formally we need to define two functions. First we have $Lsub:(\omega{_C}{_K})^2 \rightarrow \omega{_C}{_K}$ defined by: $$Lsub(\alpha,\beta)=0 \qquad if \, \alpha > \beta$$ $$Lsub(\alpha,\beta)=\{\,\gamma\,|\,\alpha+\gamma=\beta\,\} \qquad if \, \alpha \le \beta$$ We have the function $T:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ which describes how long a program runs on a given input (before halting). Define a function $sumT:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ as: $$sumT(x)=\sum_{i=0}^{i<x} T(i)$$

Now suppose we want to find $SeqState(t)$ and $SeqValue(t)$. Suppose we have $\alpha$ equal to "number of times" we have $SeqState(x)=n$ for $x<t$. Define $SeqState(t)=State(Lsub(SumT(\alpha),t),\alpha)$ and $SeqValue(t)=Value(Lsub(SumT(\alpha),t),\alpha)$.

(3) Defining step-recursive (to make the question self-contained): Given a computable well-ordering $\preceq$ of $\Bbb{N}$ with order-type $\alpha$, $address$ is meant to be the unique order-preserving bijection from $\alpha$ to $(\Bbb{N},\preceq)$.

Suppose for some recursive well-ordering of $\alpha$ we are given the notation function $address:\alpha\rightarrow \Bbb{N}$. For some function $F:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ (we can assume $F(x) \le x$ for all values in domain) we can write representation function of $F$ (in the given well-ordering for $\alpha$) as $f:\mathbb{N} \rightarrow \mathbb{N}$ and defined by: $$f(address(x))=address(F(x)) \qquad for \; all \; x\in \alpha$$

We can say that the function $F$ is step-recursive iff for arbitrarily large elements $\alpha < \omega{_C}{_K}$ there exists atleast one recursive well-ordering (of $\mathbb{N}$) with order-type $\alpha$ such that the representation function of $F$ is recursive in the given well-ordering.

$\endgroup$
  • $\begingroup$ The question is already long enough as it is so these further points haven't been mentioned in question. (1) Firstly the functions $SeqState$ and $SeqValue$ might be replaced with $State$ and $Value$. We could probably make an equivalent definition by using representation functions for functions of two or more variables. (2) Secondly we can also define trace-recursive functions for more than one variable. (3) We can also try to define partial functions too (sequential formulation will not be appropriate for that) but I am not clear on the utility of partial functions. (CONTINUED) $\endgroup$ – SSequence Oct 1 '17 at 10:38
  • $\begingroup$ (4) I have skipped on some further questions. (5) Also, the original motivation was to capture "reasonable functions", but I wasn't aware of bad notations at that time. So it is a "reverse question" in some sense perhaps. $\endgroup$ – SSequence Oct 1 '17 at 10:38
  • $\begingroup$ "We say that a function $F:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ is trace-recursive iff the function $SeqState$ and the functions $SeqValue_i$(for all variables in the program) are all step-recursive." There is a problem with this definition in the sense that it differs somewhat from the intended intuition (but it seems that can be fixed easily). The intention (as one can guess) is that for **one** specific well-ordering of order-type $\alpha$ (which can be arbitrarily large) we have all the corresponding representation functions (for the relevant functions) recursive. (continued) $\endgroup$ – SSequence Oct 3 '17 at 8:57
  • $\begingroup$ It seems that the definition above differs from that (in the sense of allowing more possibilities). A simple way is to give a definition of two (or more) functions such as $F_1:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ and $F_2:\omega{_C}{_K} \rightarrow \omega{_C}{_K}$ being "simultaneously step-recursive". This can then be used in the definition of trace-recursive functions. I haven't made that edit in the original question, but if there is some interest in the question in terms of comments or answers, then I might make this change. Anyway I hope the main point is clear with these comments. $\endgroup$ – SSequence Oct 3 '17 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.