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.