- #1
SSequence
- 556
- 95
I came up with the following qualification condition (for which I am asking for a counterexample).
Some Background:
A notation can be thought of as a mapping from an ordinal p∈ωCK to a subset of natural numbers.
Generally there can be a few variations it seems:
-- one can decide whether to use all elements of N or a proper sub-set of N in the mapping
-- one can decide whether two different numbers (say 7 and 11) can be assigned to the same element (say q∈ωCK) or whether two different numbers must always correspond to two different elements.
In what follows below I will assume that all elements of N are used in mapping and two different numbers always must correspond to two different elements (so each element is assigned a unique number).
I will denote the appropriate mapping function as address:p→N. So assuming p ≥ ω, the function will be a 1-1 correspondence.
It is well-known that many pathological examples of (recursive) ordering functions exist. One is explained in the following link in some detail:
https://mathoverflow.net/questions/...th-the-same-order-type-recursively-isomorphicRequired Notions:
(A) Programs
Now we consider the notions that are required to formulate the condition. We need the definition of an S-while program.
An S-while program has following commands (this is entirety of commands):
i) while(v!=w)
ii) End
iii) v=0
iv) v=v+1
v) v=u[t]
The "End" command is used in place of closing brackets. Whenever a while condition fails, the next command to be executed is the one right after the End command (corresponding to the while condition).
The run time of the program is less than ωCK. If the program runs for ωCK time or more it is considered to be non-terminating(looping).
All variables start from value 0. The commands in (iii) and (iv) have the usual meaning. Before discussing the meaning of command in (v) we need to describe the evaluation of variables on limits.
Consider some limit element p. To evaluate the value of a variable (say v) we divide into two sub-cases:
(a) There is some element q < p such that q was the last position at which the value of variable v was 0.
Let's denote the value of variable v at some arbitrary time t as Value(t). Then define a set S as:
S={ Value(t) | q < t < p }
We define Value(p) as equal to supremum (least upper bound) of the set S.
(b) There is no "last" position (before p) at which the value of variable v is 0. In this case set Value(p) equal to 0.
Now let's discuss the command (v). The meaning of command can be thought of as follows (it has 3 variables v, u and t):
Set the value of variable v equal to 0 immediately on the next step. Then increase it constantly in increment of 1 until it reaches the value equal to x where:
x is the value of variable u at time t (in running of the program).
So this command takes more than unit time to execute. More specifically the time it takes to execute this command depends on value of variable u (at time t).
Finally coming to line numbers, the line numbers start from 0 (the first line) up till n-1 where n is length of program. The line number n can be reserved for the point when the program halts.
For evaluating the line number on a limit, we take the line number on a limit as the smallest "reasonable" value.
This can be defined more formally. Suppose p is the limit value at which we want to evaluate the line number. Suppose State(t) denotes the line number at time t. Define a predicate P:ω→{0,1} as:
P(s) ≡ for all q < p, there exists a t greater than q such that [ State(t)=s ]
Next define a set S as:
S={ s∈ω | P(s) is true }
We define the State(p) to be the smallest value contained in set S.
(B) Representation
Our specific concern will be with those programs that halt. So note that in that case the function describing value of some variable at some time can be described as Value:p→p. Similarly the function describing the line number can be described as State:p→ω.
Now suppose for some element p we are given the address function address:p→N. For some function F:p→p we can define (explicit) representation function of F as f:N→N and defined by:
f( address(x) ) = address( F(x) )
Note that because F(x) ≤ p (for all x in the domain) and because F is total (for our case) we don't need to worry about any extra cases here. So to keep it as brief as possible we move on.
(C) Freezing
Now finally before stating the criterion, we add one last condition to our programs. Our programs are "freezing". In the sense that the "complete snapshot" of the program (that is both the values of all variables and line numbers) can't repeat itself ever.
Suppose at some point q it occurs (repetition of "complete snapshot"). Then for all time t > q we assume that the program remains in the same line number (with the same variable values). Hence it is considered to be a non-terminating program.
Timing Criterion:
A computable less-than relation (ordering function) for a given element p∈ωCK (say non-limit) represents a standard notation only if:
There exists a freezing S-while program that runs exactly for time p and the representation functions for its line number and all its variables are recursive.Just in case there is some trivial issue (with this specific statement of the qualification condition), note that the criterion can also be stated in terms of a finite number of variables whose values must increase or decrease in a specific manner (only increment by 1 and zeroing). The condition corresponding to freezing would be that at no two different times (except initially at position 0 or 1) the values of all variables can be equal. The effects of commands in this case can be thought of as instantaneous (commands can't be placed at position 0 or 1). If on a limit (say p) a value of variable also evaluates to p it is turned to 0 by force (at p).
=====
What I am asking for is a counterexample to the condition above. I have tried hard looking for it but haven't been able to come up with one. Perhaps maybe I am not thinking in the right direction required for the counterexample.
In some sense I suppose I might be relieved seeing a counterexample (in other sense little disappointed perhaps). For now, I just want to stress on this possibility (and not on the possibility of lack of counterexamples).
A counterexample can be given in two ways here:
(1) Since the condition is supposed to be general, it would be sufficient to demonstrate an element p∈ωCK where the required condition simply can't be satisfied.
I am reasonably convinced this isn't true (for certain reasons) and have a sketch in mind. But since I haven't formally worked it out (both due to lack of complete filling in of details and lack of requisite knowledge) I suppose I might include it.
(2) Demonstrate a pathology directly (showing that it demonstrably satisfies the criterion). This would be enough.
As is usually the case, this will almost certainly also demonstrate that two different notations for an element p exist (both satisfying the given criterion) for which the mapping between them fails to be recursive. One notation will be standard and the other one will be a pathology.
Some Background:
A notation can be thought of as a mapping from an ordinal p∈ωCK to a subset of natural numbers.
Generally there can be a few variations it seems:
-- one can decide whether to use all elements of N or a proper sub-set of N in the mapping
-- one can decide whether two different numbers (say 7 and 11) can be assigned to the same element (say q∈ωCK) or whether two different numbers must always correspond to two different elements.
In what follows below I will assume that all elements of N are used in mapping and two different numbers always must correspond to two different elements (so each element is assigned a unique number).
I will denote the appropriate mapping function as address:p→N. So assuming p ≥ ω, the function will be a 1-1 correspondence.
It is well-known that many pathological examples of (recursive) ordering functions exist. One is explained in the following link in some detail:
https://mathoverflow.net/questions/...th-the-same-order-type-recursively-isomorphicRequired Notions:
(A) Programs
Now we consider the notions that are required to formulate the condition. We need the definition of an S-while program.
An S-while program has following commands (this is entirety of commands):
i) while(v!=w)
ii) End
iii) v=0
iv) v=v+1
v) v=u[t]
The "End" command is used in place of closing brackets. Whenever a while condition fails, the next command to be executed is the one right after the End command (corresponding to the while condition).
The run time of the program is less than ωCK. If the program runs for ωCK time or more it is considered to be non-terminating(looping).
All variables start from value 0. The commands in (iii) and (iv) have the usual meaning. Before discussing the meaning of command in (v) we need to describe the evaluation of variables on limits.
Consider some limit element p. To evaluate the value of a variable (say v) we divide into two sub-cases:
(a) There is some element q < p such that q was the last position at which the value of variable v was 0.
Let's denote the value of variable v at some arbitrary time t as Value(t). Then define a set S as:
S={ Value(t) | q < t < p }
We define Value(p) as equal to supremum (least upper bound) of the set S.
(b) There is no "last" position (before p) at which the value of variable v is 0. In this case set Value(p) equal to 0.
Now let's discuss the command (v). The meaning of command can be thought of as follows (it has 3 variables v, u and t):
Set the value of variable v equal to 0 immediately on the next step. Then increase it constantly in increment of 1 until it reaches the value equal to x where:
x is the value of variable u at time t (in running of the program).
So this command takes more than unit time to execute. More specifically the time it takes to execute this command depends on value of variable u (at time t).
Finally coming to line numbers, the line numbers start from 0 (the first line) up till n-1 where n is length of program. The line number n can be reserved for the point when the program halts.
For evaluating the line number on a limit, we take the line number on a limit as the smallest "reasonable" value.
This can be defined more formally. Suppose p is the limit value at which we want to evaluate the line number. Suppose State(t) denotes the line number at time t. Define a predicate P:ω→{0,1} as:
P(s) ≡ for all q < p, there exists a t greater than q such that [ State(t)=s ]
Next define a set S as:
S={ s∈ω | P(s) is true }
We define the State(p) to be the smallest value contained in set S.
(B) Representation
Our specific concern will be with those programs that halt. So note that in that case the function describing value of some variable at some time can be described as Value:p→p. Similarly the function describing the line number can be described as State:p→ω.
Now suppose for some element p we are given the address function address:p→N. For some function F:p→p we can define (explicit) representation function of F as f:N→N and defined by:
f( address(x) ) = address( F(x) )
Note that because F(x) ≤ p (for all x in the domain) and because F is total (for our case) we don't need to worry about any extra cases here. So to keep it as brief as possible we move on.
(C) Freezing
Now finally before stating the criterion, we add one last condition to our programs. Our programs are "freezing". In the sense that the "complete snapshot" of the program (that is both the values of all variables and line numbers) can't repeat itself ever.
Suppose at some point q it occurs (repetition of "complete snapshot"). Then for all time t > q we assume that the program remains in the same line number (with the same variable values). Hence it is considered to be a non-terminating program.
Timing Criterion:
A computable less-than relation (ordering function) for a given element p∈ωCK (say non-limit) represents a standard notation only if:
There exists a freezing S-while program that runs exactly for time p and the representation functions for its line number and all its variables are recursive.Just in case there is some trivial issue (with this specific statement of the qualification condition), note that the criterion can also be stated in terms of a finite number of variables whose values must increase or decrease in a specific manner (only increment by 1 and zeroing). The condition corresponding to freezing would be that at no two different times (except initially at position 0 or 1) the values of all variables can be equal. The effects of commands in this case can be thought of as instantaneous (commands can't be placed at position 0 or 1). If on a limit (say p) a value of variable also evaluates to p it is turned to 0 by force (at p).
=====
What I am asking for is a counterexample to the condition above. I have tried hard looking for it but haven't been able to come up with one. Perhaps maybe I am not thinking in the right direction required for the counterexample.
In some sense I suppose I might be relieved seeing a counterexample (in other sense little disappointed perhaps). For now, I just want to stress on this possibility (and not on the possibility of lack of counterexamples).
A counterexample can be given in two ways here:
(1) Since the condition is supposed to be general, it would be sufficient to demonstrate an element p∈ωCK where the required condition simply can't be satisfied.
I am reasonably convinced this isn't true (for certain reasons) and have a sketch in mind. But since I haven't formally worked it out (both due to lack of complete filling in of details and lack of requisite knowledge) I suppose I might include it.
(2) Demonstrate a pathology directly (showing that it demonstrably satisfies the criterion). This would be enough.
As is usually the case, this will almost certainly also demonstrate that two different notations for an element p exist (both satisfying the given criterion) for which the mapping between them fails to be recursive. One notation will be standard and the other one will be a pathology.
Last edited: