Can you have indirect memory addressing in primitive recursive functions?
$begingroup$
Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid".
I'm unclear whether cell variables require constant indices or whether indirection is allowed.
The four examples shown in the book show constants. For example:
CELL(0) ⇐ 2;
What is unclear is whether this would be allowed:
CELL(CELL(0)) ⇐ 2;
The question is important to understanding the chapter. If indirection is not allowed, is that because it would defeat the objective of the language which is intentionally limited so that it can only express primitive recursive functions.
Another way of asking the question is: "Does support for indirect addressing turn BlooP into FlooP, something that can express μ-recursive functions?"
The converse of the question is: "Would the absence of indirect addressing from BlooP prevent it from writing sorts or turing machines, both of which need indirect addressing?"
logic computer-science recursion computability
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
$endgroup$
add a comment |
$begingroup$
Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid".
I'm unclear whether cell variables require constant indices or whether indirection is allowed.
The four examples shown in the book show constants. For example:
CELL(0) ⇐ 2;
What is unclear is whether this would be allowed:
CELL(CELL(0)) ⇐ 2;
The question is important to understanding the chapter. If indirection is not allowed, is that because it would defeat the objective of the language which is intentionally limited so that it can only express primitive recursive functions.
Another way of asking the question is: "Does support for indirect addressing turn BlooP into FlooP, something that can express μ-recursive functions?"
The converse of the question is: "Would the absence of indirect addressing from BlooP prevent it from writing sorts or turing machines, both of which need indirect addressing?"
logic computer-science recursion computability
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
$endgroup$
1
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19
add a comment |
$begingroup$
Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid".
I'm unclear whether cell variables require constant indices or whether indirection is allowed.
The four examples shown in the book show constants. For example:
CELL(0) ⇐ 2;
What is unclear is whether this would be allowed:
CELL(CELL(0)) ⇐ 2;
The question is important to understanding the chapter. If indirection is not allowed, is that because it would defeat the objective of the language which is intentionally limited so that it can only express primitive recursive functions.
Another way of asking the question is: "Does support for indirect addressing turn BlooP into FlooP, something that can express μ-recursive functions?"
The converse of the question is: "Would the absence of indirect addressing from BlooP prevent it from writing sorts or turing machines, both of which need indirect addressing?"
logic computer-science recursion computability
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
$endgroup$
Douglas Hofstadter describes a programming language called BlooP in his book, "Gödel, Escher, Bach: An Eternal Golden Braid".
I'm unclear whether cell variables require constant indices or whether indirection is allowed.
The four examples shown in the book show constants. For example:
CELL(0) ⇐ 2;
What is unclear is whether this would be allowed:
CELL(CELL(0)) ⇐ 2;
The question is important to understanding the chapter. If indirection is not allowed, is that because it would defeat the objective of the language which is intentionally limited so that it can only express primitive recursive functions.
Another way of asking the question is: "Does support for indirect addressing turn BlooP into FlooP, something that can express μ-recursive functions?"
The converse of the question is: "Would the absence of indirect addressing from BlooP prevent it from writing sorts or turing machines, both of which need indirect addressing?"
logic computer-science recursion computability
logic computer-science recursion computability
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
asked Dec 8 '18 at 19:36
Raymond HettingerRaymond Hettinger
46119
46119
1
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19
add a comment |
1
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19
1
1
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.
So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.
Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.
For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.
What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).
Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.
The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.
And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031529%2fcan-you-have-indirect-memory-addressing-in-primitive-recursive-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.
So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.
Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.
For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.
What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).
Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.
The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.
And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
$endgroup$
add a comment |
$begingroup$
Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.
So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.
Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.
For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.
What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).
Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.
The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.
And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
$endgroup$
add a comment |
$begingroup$
Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.
So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.
Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.
For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.
What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).
Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.
The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.
And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
$endgroup$
Well, first of all you might see that these programs came about from this paper (actually, I don't know, but I think so). So, in terms of the required computational strength, all you really need is a command to (1) zero out a variable (2) add by 1 (3) make a loop.
So, for example, if we used a command like $C[100]=C[100]+1$, we could simply replace them with a command like $t_{100}=t_{100}+1$ etc. But it seems that your question is certainly more complicated. For example, can we introduce a command like $C[C[100]]:=50$ without altering the strength of the our programs. Let's write the previous command simply as $C^2 [100]:=50$ from now on.
Below is a very brief and rough sketch. Honestly, partly why this is so brief is because I am not smart enough to see through the most important parts without writing out all the details. But this is essentially the usual reduction argument.
For example, first of all (for convenience) let's talk about commands with just one level of indirection is allowed. So $C^2 [100]$ would be allowed but not $C^3[100]$. Now it seems that the most important commands we need to be able to emulate would be of the format: $(1)$ $C^2[100]:=0$ $(2)$ $C^2[100]:=C^2 [100]+1$ $(3)$ $Loop,,,,C^2[100] $.
What we really want is that for any given program $N$ which allows nested commands (such as the three mentioned above), to be able to convert into a program $P$ which simply doesn't use any of the nested commands. So my suggestion is to use two lists $L_1$ and $L_2$ in our program $P$ (alternatively, we could just use a simple list of pairs). Both $L_1$ and $L_2$ will be of same length. $L_1$ doesn't have any repetition in its elements and $L_2$ only contains positive numbers. As as example, if we had $L_1=[0,2,4]$ and $L_2=[1,3,3]$, this is supposed to represent $C[0]=1,C[2]=3,C[4]=3$ (and furthermore, all other cell positions are $0$).
Now normally the programs $N$ and $P$ will be the same, except for those lines where $N$ makes reference to its cells. For example, if $C[100]$ or $C^2[100]$ are used in some line in $N$ we have to be careful about how it will be converted in $P$. Let's first consider what happens when $N$ uses a command such as $C[100]:=C[100]+1$ or $C[100]:=0$. Well, in that case, the program $P$ can just modify the lists $L_1$ and $L_2$ appropriately. Now what happens if $N$ uses a command such as $Loop,,,, C[100]$. Well we first find the position in $L_1$ (if it exists) which contains $100$ and look at the corresponding position in $L_2$. For example, suppose we had $L_1(3)=100$, $L_2(3)=50$. In our program $P$ we can just write the command "$Loop,,,,50$" now. If it happened that $L_1$ didn't contain $100$, then we could just write "$Loop,,,,0$" in our program $P$.
The situation shouldn't be very different (I think) when $N$ uses something like $C^2[100]$. For example, here is a rough sketch as to how we might proceed (in our program $P$): In our program $P$ check whether $L_1$ contains $100$ or not (meaning we are checking whether $C[100]$ is $0$ or not). Hypothetically suppose $L_1$ did contain $100$. Suppose we had $L_1(3)=100$. Now check whether the value in $L_2(3)$ (this corresponds to $C[100]$) is contained in $L_1$ or not? Meaning that now we are trying to check whether $C[C[100]]$ is $0$ or not. Suppose it was contained in $L_1$ at index/position $5$. Now $L_2(5)$ will correspond to $C[C[100]]$.
And now depending on the command we take the appropriate action. For example, if the command was $C^2[100]:=C^2[100]+1$ and $C[100]$ wasn't present in $L_1$, then the program $P$ will add it to $L_1$ and set the corresponding position in $L_2$ to $1$. If $C[100]$ was present in $L_1$, then $P$ will add $1$ to corresponding position in $L_2$. That is, set $L_2(i):=L_2(i)+1$ where $L_1(i)=C[100]$.
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
edited Dec 9 '18 at 2:15
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
answered Dec 9 '18 at 1:28
SSequenceSSequence
50528
50528
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031529%2fcan-you-have-indirect-memory-addressing-in-primitive-recursive-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
I don't know what you are trying to learn, but Hofstadter's book is a bad place to start if you want a rigorous introduction to recursion theory. The answer to the first part of your question is (probably) "no": i.e., allowing multiple levels of indirection makes no difference to the bounded loop property that distinguishes primitive recursion from general $mu$-recursion. To answer the second part would require a formal definition of Hofstadter's Bloop (but my guess would be that you could code round the absence of indirect addressing).
$endgroup$
– Rob Arthan
Dec 9 '18 at 0:53
$begingroup$
@RobArthan Thanks for the insights. My objective is to write a compiler for BlooP. The GEB book left parts of the language inadequately specified. Some ambiguities, such as whether cell variables are local or can be shared between procedures, can be resolved for or against without breaking the fundamental invariant of the language (can only express primitive recursive functions). However, the question of indirect addressing seems more fundamental, possibly breaking needed expressiveness by omission or breaking out to μ-recursion by inclusion.
$endgroup$
– Raymond Hettinger
Dec 9 '18 at 1:07
$begingroup$
I don't think indirect addressing adds anything to primitive recursion. If $a$ and $b$ are arrays and $i$ is an index into $b$, the search to evaluate $a[b[i]]$ is bounded above by a number that your code could have kept track of, namely the largest number stored in array $b$.
$endgroup$
– Rob Arthan
Dec 9 '18 at 1:19