Mixing
Is this proof Ok? ( about computing languages with no loops)
$begingroup$
I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter.
What's wrong with the following argument:
If there's an interpreter int let's define
the program p:
read x;
y=x;
int(x,y) //I just copy the code of int that ends with:
write output;
Now if we run p on p we get an infinite loop.
Edit:
I assume the language is non recursive but has assignments and conditional statements, creating pair and accessing their coordinates. Programs are lists that can read as inputs. Something like Scheme. (If any of these assumptions can be relaxed it's interesting too.)
I know how to prove the theorem. I wonder about this (suspicious) proof.
computer-science computational-complexity computability
asked Jan 13 at 22:19
OMGshOMGsh
284
$endgroup$
add a comment |
$begingroup$
I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter.
What's wrong with the following argument:
If there's an interpreter int let's define
the program p:
read x;
y=x;
int(x,y) //I just copy the code of int that ends with:
write output;
Now if we run p on p we get an infinite loop.
Edit:
I assume the language is non recursive but has assignments and conditional statements, creating pair and accessing their coordinates. Programs are lists that can read as inputs. Something like Scheme. (If any of these assumptions can be relaxed it's interesting too.)
I know how to prove the theorem. I wonder about this (suspicious) proof.
computer-science computational-complexity computability
asked Jan 13 at 22:19
OMGshOMGsh
284
$endgroup$
add a comment |
$begingroup$
I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter.
What's wrong with the following argument:
If there's an interpreter int let's define
the program p:
read x;
y=x;
int(x,y) //I just copy the code of int that ends with:
write output;
Now if we run p on p we get an infinite loop.
Edit:
I assume the language is non recursive but has assignments and conditional statements, creating pair and accessing their coordinates. Programs are lists that can read as inputs. Something like Scheme. (If any of these assumptions can be relaxed it's interesting too.)
I know how to prove the theorem. I wonder about this (suspicious) proof.
computer-science computational-complexity computability
asked Jan 13 at 22:19
OMGshOMGsh
284
$endgroup$
I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter.
What's wrong with the following argument:
If there's an interpreter int let's define
the program p:
read x;
y=x;
int(x,y) //I just copy the code of int that ends with:
write output;
Now if we run p on p we get an infinite loop.
Edit:
I assume the language is non recursive but has assignments and conditional statements, creating pair and accessing their coordinates. Programs are lists that can read as inputs. Something like Scheme. (If any of these assumptions can be relaxed it's interesting too.)
I know how to prove the theorem. I wonder about this (suspicious) proof.
computer-science computational-complexity computability
computer-science computational-complexity computability
asked Jan 13 at 22:19
OMGshOMGsh
284
asked Jan 13 at 22:19
OMGshOMGsh
284
edited Jan 14 at 15:34
OMGsh
asked Jan 13 at 22:19
OMGshOMGsh
284
asked Jan 13 at 22:19
OMGshOMGsh
284
asked Jan 13 at 22:19
OMGshOMGsh
284
284
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Interesting. Let's formalize your argument.
Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)
Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$
Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.
However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.
answered Jan 13 at 23:18
TedTed
21.8k13260
$endgroup$
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
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%2f3072597%2fis-this-proof-ok-about-computing-languages-with-no-loops%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$
Interesting. Let's formalize your argument.
Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)
Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$
Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.
However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.
answered Jan 13 at 23:18
TedTed
21.8k13260
$endgroup$
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
add a comment |
$begingroup$
Interesting. Let's formalize your argument.
Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)
Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$
Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.
However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.
answered Jan 13 at 23:18
TedTed
21.8k13260
$endgroup$
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
add a comment |
$begingroup$
Interesting. Let's formalize your argument.
Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)
Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$
Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.
However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.
answered Jan 13 at 23:18
TedTed
21.8k13260
$endgroup$
Interesting. Let's formalize your argument.
Assume our programs take a natural number parameter as input, the programs are numbered $f_1, f_2, f_3, ldots$, and an interpreter $I$ is a function satisfying $$I(m,n) = f_m(n).$$ The claim is that $I ne f_k$ for any $k$ (where the pair of inputs to $I$ is encoded as a single natural number input to $f_k$ in some reasonable way, and $f_k$ decodes it as needed. I won't worry about these details and just write $f_k$ as if it took 2 parameters. Here we are making the implicit assumption that our language is powerful enough to do this encoding and decoding. Indeed the result is false for very weak languages.)
Assume that $I = f_k$ and define $p(n) = f_k(n,n)$. Then $p$ is also a program in our language (again, we are assuming that our language is powerful enough for this construction), and hence $p = f_j$ for some $j$. Thus $f_j(n) = f_k(n,n)$. Now let $n=j$ and we get $$f_j(j) = f_k(j, j) = I(j,j).$$
Unfortunately, as you can see by comparing this to the previous displayed equation, we have not reached a contradiction, so this argument does not quite work. The problem is that the "infinite loop" you get from "running" the program in the interpreter assumes that the interpreter will run the program step by step. But there's actually no such requirement. The interpreter could be any function satisfying $I(m,n)=f_m(n)$ and we have no idea what the implementation may be.
However, the argument is easily fixed. Just define instead $p(n) = f_k(n,n) + 1$ (here I am assuming the outputs of our functions are encoded as natural numbers too, and the language is powerful enough to do the +1 operation). Then repeating the above argument we get $$f_j(j) = f_k(j,j) + 1 = I(j,j) + 1$$ and now this is a contradiction because $f_j(j) = I(j,j)$ by definition.
answered Jan 13 at 23:18
TedTed
21.8k13260
answered Jan 13 at 23:18
TedTed
21.8k13260
answered Jan 13 at 23:18
TedTed
21.8k13260
answered Jan 13 at 23:18
TedTed
21.8k13260
21.8k13260
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
add a comment |
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
$begingroup$
Thanks for your detailed answer. I like your argument "The proof assumes that the interpreter will run the program step by step". But maybe there's some kind of a lower bound for the running time of any valid interpreter (say, as a function of the input length)? I know the correct proof in your answer, i simply wonder whether this version is essentially wrong or maybe it can be fixed.
$endgroup$
– OMGsh
Jan 14 at 14:52
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%2f3072597%2fis-this-proof-ok-about-computing-languages-with-no-loops%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
