A constructivist reading of the Church-Turing thesis











up vote
2
down vote

favorite












I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" and $R(f)$ for "$f$ is recursive", then $EC(f) rightarrow R(f)$.



Now, in a constructivist reading, $EC(f) rightarrow R(f)$ holds iff we have a total constructive function $h(x, y)$ such that, for every effectively computable $f$, for every $pi$ proof of $EC(f)$, $h(f, pi)$ is a proof of $R(f)$. However, it is generally admitted that "total constructive function" means nothing but "effectively computable function". So, if $h(x, y)$ is a total constructive function, it is an effectively computable function, and hence it should be, so to say, auto-applicable, i.e., it should be able to prove of itself that, if it is an effectively computable function, then it is a recursive function, i.e. again, for every $pi$ proof of $EC(h(x, y))$, $h(h(x, y), pi)$ is a proof of $R(h(x, y))$.



I was wondering if an auto-applicability of this kind, together with what $h(x, y)$ is supposedly expected to do, may create some problematic diagonalizations. What would you think about that?










share|cite|improve this question






















  • I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
    – Dan Doel
    Nov 13 at 0:52










  • Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
    – Dan Doel
    Nov 13 at 0:57










  • Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
    – Antpicc
    Nov 13 at 8:09










  • Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
    – Antpicc
    Nov 13 at 8:16















up vote
2
down vote

favorite












I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" and $R(f)$ for "$f$ is recursive", then $EC(f) rightarrow R(f)$.



Now, in a constructivist reading, $EC(f) rightarrow R(f)$ holds iff we have a total constructive function $h(x, y)$ such that, for every effectively computable $f$, for every $pi$ proof of $EC(f)$, $h(f, pi)$ is a proof of $R(f)$. However, it is generally admitted that "total constructive function" means nothing but "effectively computable function". So, if $h(x, y)$ is a total constructive function, it is an effectively computable function, and hence it should be, so to say, auto-applicable, i.e., it should be able to prove of itself that, if it is an effectively computable function, then it is a recursive function, i.e. again, for every $pi$ proof of $EC(h(x, y))$, $h(h(x, y), pi)$ is a proof of $R(h(x, y))$.



I was wondering if an auto-applicability of this kind, together with what $h(x, y)$ is supposedly expected to do, may create some problematic diagonalizations. What would you think about that?










share|cite|improve this question






















  • I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
    – Dan Doel
    Nov 13 at 0:52










  • Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
    – Dan Doel
    Nov 13 at 0:57










  • Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
    – Antpicc
    Nov 13 at 8:09










  • Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
    – Antpicc
    Nov 13 at 8:16













up vote
2
down vote

favorite









up vote
2
down vote

favorite











I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" and $R(f)$ for "$f$ is recursive", then $EC(f) rightarrow R(f)$.



Now, in a constructivist reading, $EC(f) rightarrow R(f)$ holds iff we have a total constructive function $h(x, y)$ such that, for every effectively computable $f$, for every $pi$ proof of $EC(f)$, $h(f, pi)$ is a proof of $R(f)$. However, it is generally admitted that "total constructive function" means nothing but "effectively computable function". So, if $h(x, y)$ is a total constructive function, it is an effectively computable function, and hence it should be, so to say, auto-applicable, i.e., it should be able to prove of itself that, if it is an effectively computable function, then it is a recursive function, i.e. again, for every $pi$ proof of $EC(h(x, y))$, $h(h(x, y), pi)$ is a proof of $R(h(x, y))$.



I was wondering if an auto-applicability of this kind, together with what $h(x, y)$ is supposedly expected to do, may create some problematic diagonalizations. What would you think about that?










share|cite|improve this question













I recently asked myself a question concerning a constructivist reading of the Church-Turing thesis. Let us give the latter in the following formulation: put $EC(f)$ for "$f$ is effectively computable" and $R(f)$ for "$f$ is recursive", then $EC(f) rightarrow R(f)$.



Now, in a constructivist reading, $EC(f) rightarrow R(f)$ holds iff we have a total constructive function $h(x, y)$ such that, for every effectively computable $f$, for every $pi$ proof of $EC(f)$, $h(f, pi)$ is a proof of $R(f)$. However, it is generally admitted that "total constructive function" means nothing but "effectively computable function". So, if $h(x, y)$ is a total constructive function, it is an effectively computable function, and hence it should be, so to say, auto-applicable, i.e., it should be able to prove of itself that, if it is an effectively computable function, then it is a recursive function, i.e. again, for every $pi$ proof of $EC(h(x, y))$, $h(h(x, y), pi)$ is a proof of $R(h(x, y))$.



I was wondering if an auto-applicability of this kind, together with what $h(x, y)$ is supposedly expected to do, may create some problematic diagonalizations. What would you think about that?







logic recursion computability






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Nov 12 at 16:39









Antpicc

284




284












  • I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
    – Dan Doel
    Nov 13 at 0:52










  • Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
    – Dan Doel
    Nov 13 at 0:57










  • Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
    – Antpicc
    Nov 13 at 8:09










  • Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
    – Antpicc
    Nov 13 at 8:16


















  • I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
    – Dan Doel
    Nov 13 at 0:52










  • Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
    – Dan Doel
    Nov 13 at 0:57










  • Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
    – Antpicc
    Nov 13 at 8:09










  • Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
    – Antpicc
    Nov 13 at 8:16
















I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
– Dan Doel
Nov 13 at 0:52




I don't know if this exactly answers the question, but this is probably related: mathoverflow.net/questions/141339/… It is slightly different in that it's adding the principle that all functions are computable to a theory in which all definable functions are computable.
– Dan Doel
Nov 13 at 0:52












Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
– Dan Doel
Nov 13 at 0:57




Note that there are models where the principle is sound. However, those same models tend not to justify other 'nice' properties of functions, and the ones with nice functions don't justify Church's law. So whether there's a problematic diagonalization may depend on the exact other content of the theory.
– Dan Doel
Nov 13 at 0:57












Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
– Antpicc
Nov 13 at 8:09




Thanks for your answer! I must confess I'm not enough into such kind of stuff to fully understand Harper's arguments, nor how they relate to my questions. Would you mind please explaining me these points?
– Antpicc
Nov 13 at 8:09












Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
– Antpicc
Nov 13 at 8:16




Also, my real question (although I was not so explicit above) is: how could a diagonalization be problematic? This I cannot see...
– Antpicc
Nov 13 at 8:16










2 Answers
2






active

oldest

votes

















up vote
0
down vote













Ok, so, as far as I understand, there seems to be two arguments that may concern my question. The first stems from the observation that, in an extensional approach, a Church function $(N to N) to N$ is injective and, provided it also is surjective or decidable, one easily derive a contradiction. However, this argument fails in that there are models providing an injective function $(N to N) to N$.



The second is instead based on the fact that, thanks to Kleene $T$ predicate, one can encode an algorithm $h(x, x) : (N to N) to N$ deciding whether programs halt or not. One can then define a diagonal function $$[lambda x : N. neg h(x, x)] : N to N$$ for which the Church function would give us a code, say $n$. But then, we have a contradiction when we consider $$h(n, n)$$ However, I can't see how the contradiction is derived here, it maybe is $$h(n, n) = 1 leftrightarrow d(n) text{halts} leftrightarrow neg h(n, n) = 1 leftrightarrow h(n, n) = 0$$ is that correct?



However, the problem with Church's thesis here does not really derive from the fact that computable functions are proved to be recursive by an auto-applicable computable function. It derives from the decidability of function equality, which, again if I am not wrong, implies that one can encode a decision algorithm.






share|cite|improve this answer























  • So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
    – Dan Doel
    Nov 14 at 2:33










  • So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
    – Dan Doel
    Nov 14 at 2:40










  • Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
    – Antpicc
    2 days ago




















up vote
0
down vote













This still isn't a definite answer to your question, but a comment would not cut it.



The source of issues (I think) in the presentation of "Church's law" above is that is a statement about functions:



$$∀ f : ℕ → ℕ. R(f)$$



where:



$$R(f) = ∃ n. ∀ m. T(n,m,f(m))$$



or something of that sort. Interpreted in the usual propositions-as-types way, this kind of says that 'source code' must be recoverable from a function. This is easy if $ℕ → ℕ$ just is source code (i.e. $ℕ$), and you just give it back. But this does not validate extensional equality, because there may be many pieces of source that compute the same extensional function. If you want to have extensionality, you are forced to pick a canonical implementation for each function, which leads to decidability of functions.



However, you have not stated Church's thesis this way. You said:



$$h : ∀f. EC(f) → R(f)$$



and further, something like:



$$w_h : EC(h)$$



(Imagining that we've worked out exactly how to make that well-typed.) And these aren't necessarily subject to the same pitfalls. First, Church's law has extra 'evidence' in play, the proof of $EC(f)$. We don't need to map functions to their (recursive) source code, we need to map justifications of their 'effective computability' to their source code. But the justification of effective computability might just be a different sort of source code, so this isn't as far fetched. In fact, there might be multiple ways of proving $EC(f)$ that translate to different proofs of $R(f)$, even though we don't care about the difference since they're "propositions." So we might have:



$$f : ℕ → ℕ, w_f : EC(f)$$
$$g : ℕ → ℕ, w_g : EC(g)$$



with:



$$∀ m. f(m) = g(m)$$



but:



$$w_f neq w_g$$



which is fine. We can only decide equality of $Σ_{f:ℕ→ℕ}EC(f)$ with this way of writing Church's thesis.



Also, I think the idea behind having $w_h$ is all right. If you don't mind my switching things around, one way of presenting all this might be with a modality. The idea is that $square A$ is like the 'effectively computable' subcollection of $A$, or maybe an internal reflection of the 'source code' of $A$ values. So $square(ℕ → ℕ)$ is the collection of things that we know can be used to compute a function, but we may be at more liberty to introspect them. One thing we expect to have is:



$$u : square A → A$$



which allows us to apply our source code (and serves the role of $T$). But also we might have your Church's thesis, which might be like:



$$h : square(ℕ → ℕ) → ℕ$$



which gives us some concrete way of looking at the particular function definition we're dealing with (without having to come up with some way of saying how you can inspect a $square$ type). Maybe we could even be more general and say:



$$h_A : square A → ℕ$$



and then also:



$$w_A : square(square A → ℕ)$$



with:



$$u(w_A) = h_A$$



I'm not certain this all works out with an ability to still have extensional equality of functions, but observe 'source code' of boxed functions, etc. But it is very similar to actual structure that arises in realizability and modest sets.



In this format, the problematic "Church's law" is:



$$(ℕ → ℕ) → square(ℕ → ℕ)$$



which is like a modal collapse, and not something we'd normally expect.



So, I think if you are careful enough, you may be able to have the structure you propose without paradox (and I think something like it is an exciting idea with potential applications), and maintain nice extensional principles where desired. But I don't have a proof, and it's possible someone who knows more (like Bauer) could look at this and immediately give an example of how it's wrong.






share|cite|improve this answer





















  • Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
    – Antpicc
    yesterday













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',
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
});


}
});














 

draft saved


draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995534%2fa-constructivist-reading-of-the-church-turing-thesis%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
0
down vote













Ok, so, as far as I understand, there seems to be two arguments that may concern my question. The first stems from the observation that, in an extensional approach, a Church function $(N to N) to N$ is injective and, provided it also is surjective or decidable, one easily derive a contradiction. However, this argument fails in that there are models providing an injective function $(N to N) to N$.



The second is instead based on the fact that, thanks to Kleene $T$ predicate, one can encode an algorithm $h(x, x) : (N to N) to N$ deciding whether programs halt or not. One can then define a diagonal function $$[lambda x : N. neg h(x, x)] : N to N$$ for which the Church function would give us a code, say $n$. But then, we have a contradiction when we consider $$h(n, n)$$ However, I can't see how the contradiction is derived here, it maybe is $$h(n, n) = 1 leftrightarrow d(n) text{halts} leftrightarrow neg h(n, n) = 1 leftrightarrow h(n, n) = 0$$ is that correct?



However, the problem with Church's thesis here does not really derive from the fact that computable functions are proved to be recursive by an auto-applicable computable function. It derives from the decidability of function equality, which, again if I am not wrong, implies that one can encode a decision algorithm.






share|cite|improve this answer























  • So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
    – Dan Doel
    Nov 14 at 2:33










  • So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
    – Dan Doel
    Nov 14 at 2:40










  • Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
    – Antpicc
    2 days ago

















up vote
0
down vote













Ok, so, as far as I understand, there seems to be two arguments that may concern my question. The first stems from the observation that, in an extensional approach, a Church function $(N to N) to N$ is injective and, provided it also is surjective or decidable, one easily derive a contradiction. However, this argument fails in that there are models providing an injective function $(N to N) to N$.



The second is instead based on the fact that, thanks to Kleene $T$ predicate, one can encode an algorithm $h(x, x) : (N to N) to N$ deciding whether programs halt or not. One can then define a diagonal function $$[lambda x : N. neg h(x, x)] : N to N$$ for which the Church function would give us a code, say $n$. But then, we have a contradiction when we consider $$h(n, n)$$ However, I can't see how the contradiction is derived here, it maybe is $$h(n, n) = 1 leftrightarrow d(n) text{halts} leftrightarrow neg h(n, n) = 1 leftrightarrow h(n, n) = 0$$ is that correct?



However, the problem with Church's thesis here does not really derive from the fact that computable functions are proved to be recursive by an auto-applicable computable function. It derives from the decidability of function equality, which, again if I am not wrong, implies that one can encode a decision algorithm.






share|cite|improve this answer























  • So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
    – Dan Doel
    Nov 14 at 2:33










  • So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
    – Dan Doel
    Nov 14 at 2:40










  • Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
    – Antpicc
    2 days ago















up vote
0
down vote










up vote
0
down vote









Ok, so, as far as I understand, there seems to be two arguments that may concern my question. The first stems from the observation that, in an extensional approach, a Church function $(N to N) to N$ is injective and, provided it also is surjective or decidable, one easily derive a contradiction. However, this argument fails in that there are models providing an injective function $(N to N) to N$.



The second is instead based on the fact that, thanks to Kleene $T$ predicate, one can encode an algorithm $h(x, x) : (N to N) to N$ deciding whether programs halt or not. One can then define a diagonal function $$[lambda x : N. neg h(x, x)] : N to N$$ for which the Church function would give us a code, say $n$. But then, we have a contradiction when we consider $$h(n, n)$$ However, I can't see how the contradiction is derived here, it maybe is $$h(n, n) = 1 leftrightarrow d(n) text{halts} leftrightarrow neg h(n, n) = 1 leftrightarrow h(n, n) = 0$$ is that correct?



However, the problem with Church's thesis here does not really derive from the fact that computable functions are proved to be recursive by an auto-applicable computable function. It derives from the decidability of function equality, which, again if I am not wrong, implies that one can encode a decision algorithm.






share|cite|improve this answer














Ok, so, as far as I understand, there seems to be two arguments that may concern my question. The first stems from the observation that, in an extensional approach, a Church function $(N to N) to N$ is injective and, provided it also is surjective or decidable, one easily derive a contradiction. However, this argument fails in that there are models providing an injective function $(N to N) to N$.



The second is instead based on the fact that, thanks to Kleene $T$ predicate, one can encode an algorithm $h(x, x) : (N to N) to N$ deciding whether programs halt or not. One can then define a diagonal function $$[lambda x : N. neg h(x, x)] : N to N$$ for which the Church function would give us a code, say $n$. But then, we have a contradiction when we consider $$h(n, n)$$ However, I can't see how the contradiction is derived here, it maybe is $$h(n, n) = 1 leftrightarrow d(n) text{halts} leftrightarrow neg h(n, n) = 1 leftrightarrow h(n, n) = 0$$ is that correct?



However, the problem with Church's thesis here does not really derive from the fact that computable functions are proved to be recursive by an auto-applicable computable function. It derives from the decidability of function equality, which, again if I am not wrong, implies that one can encode a decision algorithm.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 13 at 10:05

























answered Nov 13 at 9:59









Antpicc

284




284












  • So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
    – Dan Doel
    Nov 14 at 2:33










  • So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
    – Dan Doel
    Nov 14 at 2:40










  • Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
    – Antpicc
    2 days ago




















  • So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
    – Dan Doel
    Nov 14 at 2:33










  • So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
    – Dan Doel
    Nov 14 at 2:40










  • Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
    – Antpicc
    2 days ago


















So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
– Dan Doel
Nov 14 at 2:33




So, I think to see any sort of problem, one has to ask what $EC$ and $R$ actually are. Perhaps $R$ moreso. What is the specification of a function being recursive? I think the interpretation used in Harper's argument is that a number is produced that somehow identifies which recursive definition gives the function. Equality of natural numbers is decidable, so injectivity yields a decision procedure on functions.
– Dan Doel
Nov 14 at 2:33












So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
– Dan Doel
Nov 14 at 2:40




So, I guess the other question to ask is whether $EC(f) to R(f)$ is sort of 'trivial'. In the models where "Church's law" holds (or at least, the ones Andrej Bauer says he knows about, and he'd know better than me), it's trivial, because 'functions' $ℕ → ℕ$ are already numbers representing the function, and you may have distinguishable representatives of the same extensional function. So, perhaps couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself.
– Dan Doel
Nov 14 at 2:40












Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
– Antpicc
2 days ago






Thanks for your answer. Indeed, I have been told by an experienced professor I asked the question, that my issue is pointless, for the Church-Turing thesis states the equivalence of the two classes $EC$ and $R$ - it is, so to say, a kind of definition of the concept of a function being computable in terms of a more precise notion such as recursiveness. However, I have not very well understood where you say "couching in terms of $EC(h)$ and $R(h)$ solves the problem, because they are separate witnesses that don't constrain your representation of the function $h$ itself".
– Antpicc
2 days ago












up vote
0
down vote













This still isn't a definite answer to your question, but a comment would not cut it.



The source of issues (I think) in the presentation of "Church's law" above is that is a statement about functions:



$$∀ f : ℕ → ℕ. R(f)$$



where:



$$R(f) = ∃ n. ∀ m. T(n,m,f(m))$$



or something of that sort. Interpreted in the usual propositions-as-types way, this kind of says that 'source code' must be recoverable from a function. This is easy if $ℕ → ℕ$ just is source code (i.e. $ℕ$), and you just give it back. But this does not validate extensional equality, because there may be many pieces of source that compute the same extensional function. If you want to have extensionality, you are forced to pick a canonical implementation for each function, which leads to decidability of functions.



However, you have not stated Church's thesis this way. You said:



$$h : ∀f. EC(f) → R(f)$$



and further, something like:



$$w_h : EC(h)$$



(Imagining that we've worked out exactly how to make that well-typed.) And these aren't necessarily subject to the same pitfalls. First, Church's law has extra 'evidence' in play, the proof of $EC(f)$. We don't need to map functions to their (recursive) source code, we need to map justifications of their 'effective computability' to their source code. But the justification of effective computability might just be a different sort of source code, so this isn't as far fetched. In fact, there might be multiple ways of proving $EC(f)$ that translate to different proofs of $R(f)$, even though we don't care about the difference since they're "propositions." So we might have:



$$f : ℕ → ℕ, w_f : EC(f)$$
$$g : ℕ → ℕ, w_g : EC(g)$$



with:



$$∀ m. f(m) = g(m)$$



but:



$$w_f neq w_g$$



which is fine. We can only decide equality of $Σ_{f:ℕ→ℕ}EC(f)$ with this way of writing Church's thesis.



Also, I think the idea behind having $w_h$ is all right. If you don't mind my switching things around, one way of presenting all this might be with a modality. The idea is that $square A$ is like the 'effectively computable' subcollection of $A$, or maybe an internal reflection of the 'source code' of $A$ values. So $square(ℕ → ℕ)$ is the collection of things that we know can be used to compute a function, but we may be at more liberty to introspect them. One thing we expect to have is:



$$u : square A → A$$



which allows us to apply our source code (and serves the role of $T$). But also we might have your Church's thesis, which might be like:



$$h : square(ℕ → ℕ) → ℕ$$



which gives us some concrete way of looking at the particular function definition we're dealing with (without having to come up with some way of saying how you can inspect a $square$ type). Maybe we could even be more general and say:



$$h_A : square A → ℕ$$



and then also:



$$w_A : square(square A → ℕ)$$



with:



$$u(w_A) = h_A$$



I'm not certain this all works out with an ability to still have extensional equality of functions, but observe 'source code' of boxed functions, etc. But it is very similar to actual structure that arises in realizability and modest sets.



In this format, the problematic "Church's law" is:



$$(ℕ → ℕ) → square(ℕ → ℕ)$$



which is like a modal collapse, and not something we'd normally expect.



So, I think if you are careful enough, you may be able to have the structure you propose without paradox (and I think something like it is an exciting idea with potential applications), and maintain nice extensional principles where desired. But I don't have a proof, and it's possible someone who knows more (like Bauer) could look at this and immediately give an example of how it's wrong.






share|cite|improve this answer





















  • Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
    – Antpicc
    yesterday

















up vote
0
down vote













This still isn't a definite answer to your question, but a comment would not cut it.



The source of issues (I think) in the presentation of "Church's law" above is that is a statement about functions:



$$∀ f : ℕ → ℕ. R(f)$$



where:



$$R(f) = ∃ n. ∀ m. T(n,m,f(m))$$



or something of that sort. Interpreted in the usual propositions-as-types way, this kind of says that 'source code' must be recoverable from a function. This is easy if $ℕ → ℕ$ just is source code (i.e. $ℕ$), and you just give it back. But this does not validate extensional equality, because there may be many pieces of source that compute the same extensional function. If you want to have extensionality, you are forced to pick a canonical implementation for each function, which leads to decidability of functions.



However, you have not stated Church's thesis this way. You said:



$$h : ∀f. EC(f) → R(f)$$



and further, something like:



$$w_h : EC(h)$$



(Imagining that we've worked out exactly how to make that well-typed.) And these aren't necessarily subject to the same pitfalls. First, Church's law has extra 'evidence' in play, the proof of $EC(f)$. We don't need to map functions to their (recursive) source code, we need to map justifications of their 'effective computability' to their source code. But the justification of effective computability might just be a different sort of source code, so this isn't as far fetched. In fact, there might be multiple ways of proving $EC(f)$ that translate to different proofs of $R(f)$, even though we don't care about the difference since they're "propositions." So we might have:



$$f : ℕ → ℕ, w_f : EC(f)$$
$$g : ℕ → ℕ, w_g : EC(g)$$



with:



$$∀ m. f(m) = g(m)$$



but:



$$w_f neq w_g$$



which is fine. We can only decide equality of $Σ_{f:ℕ→ℕ}EC(f)$ with this way of writing Church's thesis.



Also, I think the idea behind having $w_h$ is all right. If you don't mind my switching things around, one way of presenting all this might be with a modality. The idea is that $square A$ is like the 'effectively computable' subcollection of $A$, or maybe an internal reflection of the 'source code' of $A$ values. So $square(ℕ → ℕ)$ is the collection of things that we know can be used to compute a function, but we may be at more liberty to introspect them. One thing we expect to have is:



$$u : square A → A$$



which allows us to apply our source code (and serves the role of $T$). But also we might have your Church's thesis, which might be like:



$$h : square(ℕ → ℕ) → ℕ$$



which gives us some concrete way of looking at the particular function definition we're dealing with (without having to come up with some way of saying how you can inspect a $square$ type). Maybe we could even be more general and say:



$$h_A : square A → ℕ$$



and then also:



$$w_A : square(square A → ℕ)$$



with:



$$u(w_A) = h_A$$



I'm not certain this all works out with an ability to still have extensional equality of functions, but observe 'source code' of boxed functions, etc. But it is very similar to actual structure that arises in realizability and modest sets.



In this format, the problematic "Church's law" is:



$$(ℕ → ℕ) → square(ℕ → ℕ)$$



which is like a modal collapse, and not something we'd normally expect.



So, I think if you are careful enough, you may be able to have the structure you propose without paradox (and I think something like it is an exciting idea with potential applications), and maintain nice extensional principles where desired. But I don't have a proof, and it's possible someone who knows more (like Bauer) could look at this and immediately give an example of how it's wrong.






share|cite|improve this answer





















  • Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
    – Antpicc
    yesterday















up vote
0
down vote










up vote
0
down vote









This still isn't a definite answer to your question, but a comment would not cut it.



The source of issues (I think) in the presentation of "Church's law" above is that is a statement about functions:



$$∀ f : ℕ → ℕ. R(f)$$



where:



$$R(f) = ∃ n. ∀ m. T(n,m,f(m))$$



or something of that sort. Interpreted in the usual propositions-as-types way, this kind of says that 'source code' must be recoverable from a function. This is easy if $ℕ → ℕ$ just is source code (i.e. $ℕ$), and you just give it back. But this does not validate extensional equality, because there may be many pieces of source that compute the same extensional function. If you want to have extensionality, you are forced to pick a canonical implementation for each function, which leads to decidability of functions.



However, you have not stated Church's thesis this way. You said:



$$h : ∀f. EC(f) → R(f)$$



and further, something like:



$$w_h : EC(h)$$



(Imagining that we've worked out exactly how to make that well-typed.) And these aren't necessarily subject to the same pitfalls. First, Church's law has extra 'evidence' in play, the proof of $EC(f)$. We don't need to map functions to their (recursive) source code, we need to map justifications of their 'effective computability' to their source code. But the justification of effective computability might just be a different sort of source code, so this isn't as far fetched. In fact, there might be multiple ways of proving $EC(f)$ that translate to different proofs of $R(f)$, even though we don't care about the difference since they're "propositions." So we might have:



$$f : ℕ → ℕ, w_f : EC(f)$$
$$g : ℕ → ℕ, w_g : EC(g)$$



with:



$$∀ m. f(m) = g(m)$$



but:



$$w_f neq w_g$$



which is fine. We can only decide equality of $Σ_{f:ℕ→ℕ}EC(f)$ with this way of writing Church's thesis.



Also, I think the idea behind having $w_h$ is all right. If you don't mind my switching things around, one way of presenting all this might be with a modality. The idea is that $square A$ is like the 'effectively computable' subcollection of $A$, or maybe an internal reflection of the 'source code' of $A$ values. So $square(ℕ → ℕ)$ is the collection of things that we know can be used to compute a function, but we may be at more liberty to introspect them. One thing we expect to have is:



$$u : square A → A$$



which allows us to apply our source code (and serves the role of $T$). But also we might have your Church's thesis, which might be like:



$$h : square(ℕ → ℕ) → ℕ$$



which gives us some concrete way of looking at the particular function definition we're dealing with (without having to come up with some way of saying how you can inspect a $square$ type). Maybe we could even be more general and say:



$$h_A : square A → ℕ$$



and then also:



$$w_A : square(square A → ℕ)$$



with:



$$u(w_A) = h_A$$



I'm not certain this all works out with an ability to still have extensional equality of functions, but observe 'source code' of boxed functions, etc. But it is very similar to actual structure that arises in realizability and modest sets.



In this format, the problematic "Church's law" is:



$$(ℕ → ℕ) → square(ℕ → ℕ)$$



which is like a modal collapse, and not something we'd normally expect.



So, I think if you are careful enough, you may be able to have the structure you propose without paradox (and I think something like it is an exciting idea with potential applications), and maintain nice extensional principles where desired. But I don't have a proof, and it's possible someone who knows more (like Bauer) could look at this and immediately give an example of how it's wrong.






share|cite|improve this answer












This still isn't a definite answer to your question, but a comment would not cut it.



The source of issues (I think) in the presentation of "Church's law" above is that is a statement about functions:



$$∀ f : ℕ → ℕ. R(f)$$



where:



$$R(f) = ∃ n. ∀ m. T(n,m,f(m))$$



or something of that sort. Interpreted in the usual propositions-as-types way, this kind of says that 'source code' must be recoverable from a function. This is easy if $ℕ → ℕ$ just is source code (i.e. $ℕ$), and you just give it back. But this does not validate extensional equality, because there may be many pieces of source that compute the same extensional function. If you want to have extensionality, you are forced to pick a canonical implementation for each function, which leads to decidability of functions.



However, you have not stated Church's thesis this way. You said:



$$h : ∀f. EC(f) → R(f)$$



and further, something like:



$$w_h : EC(h)$$



(Imagining that we've worked out exactly how to make that well-typed.) And these aren't necessarily subject to the same pitfalls. First, Church's law has extra 'evidence' in play, the proof of $EC(f)$. We don't need to map functions to their (recursive) source code, we need to map justifications of their 'effective computability' to their source code. But the justification of effective computability might just be a different sort of source code, so this isn't as far fetched. In fact, there might be multiple ways of proving $EC(f)$ that translate to different proofs of $R(f)$, even though we don't care about the difference since they're "propositions." So we might have:



$$f : ℕ → ℕ, w_f : EC(f)$$
$$g : ℕ → ℕ, w_g : EC(g)$$



with:



$$∀ m. f(m) = g(m)$$



but:



$$w_f neq w_g$$



which is fine. We can only decide equality of $Σ_{f:ℕ→ℕ}EC(f)$ with this way of writing Church's thesis.



Also, I think the idea behind having $w_h$ is all right. If you don't mind my switching things around, one way of presenting all this might be with a modality. The idea is that $square A$ is like the 'effectively computable' subcollection of $A$, or maybe an internal reflection of the 'source code' of $A$ values. So $square(ℕ → ℕ)$ is the collection of things that we know can be used to compute a function, but we may be at more liberty to introspect them. One thing we expect to have is:



$$u : square A → A$$



which allows us to apply our source code (and serves the role of $T$). But also we might have your Church's thesis, which might be like:



$$h : square(ℕ → ℕ) → ℕ$$



which gives us some concrete way of looking at the particular function definition we're dealing with (without having to come up with some way of saying how you can inspect a $square$ type). Maybe we could even be more general and say:



$$h_A : square A → ℕ$$



and then also:



$$w_A : square(square A → ℕ)$$



with:



$$u(w_A) = h_A$$



I'm not certain this all works out with an ability to still have extensional equality of functions, but observe 'source code' of boxed functions, etc. But it is very similar to actual structure that arises in realizability and modest sets.



In this format, the problematic "Church's law" is:



$$(ℕ → ℕ) → square(ℕ → ℕ)$$



which is like a modal collapse, and not something we'd normally expect.



So, I think if you are careful enough, you may be able to have the structure you propose without paradox (and I think something like it is an exciting idea with potential applications), and maintain nice extensional principles where desired. But I don't have a proof, and it's possible someone who knows more (like Bauer) could look at this and immediately give an example of how it's wrong.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered yesterday









Dan Doel

21113




21113












  • Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
    – Antpicc
    yesterday




















  • Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
    – Antpicc
    yesterday


















Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
– Antpicc
yesterday






Thanks for the this very detailed answer! I must confess that not everything is so clear to me, but it seems that you're suggesting that I frame my formulation of Church's thesis through modal operators, and work on it in order not to have paradoxical situations. However, my question would now be: which kind of paradoxes may arise with this modalities, the ones you refer to saying "you may be able to have the structure you propose without paradox"? And would they depend on diagonalization? However, thanks a lot!
– Antpicc
yesterday




















 

draft saved


draft discarded



















































 


draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995534%2fa-constructivist-reading-of-the-church-turing-thesis%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Aardman Animations

Are they similar matrix