Definition of partial function using predicate that is possibly undecidable
$begingroup$
I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.
Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument will at moment $x$ (but not earlier) have completed the computation of a value (call that value $phi_i(a)$).
Then Kleene tells the theorem: (A) The predicate $T(i, a,x)$ is decidable. (B) $phi_i(a)$ as a partial function of $i$ and $a$ is computable.
I am not sure I understand the definition of a partial function. In the book, Kleene says that "As a function of $i$ and $a$ both, $phi_i (a)$ as we remarked is defined exactly when there exists $x$ such that $T(i,a,x)$ is true. So it is a partially defined number-theoretic function of two variables $i$ and $a$, or briefly a partial function."
My problem with this definition is that how do we know that there exists $x$ such that $T(i,a,x)$ is true? Intuitively, I feel that this condition is not decidable, i.e. there does not exist an algorithm to check this. Because if it is false then I would check each $x$ but never reach the end. Why do we allow this kind of undecidable property to be in our definition? I feel concerned about this because Turing machines are used in metamathematics, i.e. our reasoning about formal systems, and we want this reasoning to be finitary (whatever that means).
Long story short - if there is a partial function defined by undecidable property, how do I know whether for each specific value as an argument the function is defined or not. And can this create any problems?
logic turing-machines
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
$endgroup$
|
show 4 more comments
$begingroup$
I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.
Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument will at moment $x$ (but not earlier) have completed the computation of a value (call that value $phi_i(a)$).
Then Kleene tells the theorem: (A) The predicate $T(i, a,x)$ is decidable. (B) $phi_i(a)$ as a partial function of $i$ and $a$ is computable.
I am not sure I understand the definition of a partial function. In the book, Kleene says that "As a function of $i$ and $a$ both, $phi_i (a)$ as we remarked is defined exactly when there exists $x$ such that $T(i,a,x)$ is true. So it is a partially defined number-theoretic function of two variables $i$ and $a$, or briefly a partial function."
My problem with this definition is that how do we know that there exists $x$ such that $T(i,a,x)$ is true? Intuitively, I feel that this condition is not decidable, i.e. there does not exist an algorithm to check this. Because if it is false then I would check each $x$ but never reach the end. Why do we allow this kind of undecidable property to be in our definition? I feel concerned about this because Turing machines are used in metamathematics, i.e. our reasoning about formal systems, and we want this reasoning to be finitary (whatever that means).
Long story short - if there is a partial function defined by undecidable property, how do I know whether for each specific value as an argument the function is defined or not. And can this create any problems?
logic turing-machines
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
$endgroup$
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
2
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
2
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06
|
show 4 more comments
$begingroup$
I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.
Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument will at moment $x$ (but not earlier) have completed the computation of a value (call that value $phi_i(a)$).
Then Kleene tells the theorem: (A) The predicate $T(i, a,x)$ is decidable. (B) $phi_i(a)$ as a partial function of $i$ and $a$ is computable.
I am not sure I understand the definition of a partial function. In the book, Kleene says that "As a function of $i$ and $a$ both, $phi_i (a)$ as we remarked is defined exactly when there exists $x$ such that $T(i,a,x)$ is true. So it is a partially defined number-theoretic function of two variables $i$ and $a$, or briefly a partial function."
My problem with this definition is that how do we know that there exists $x$ such that $T(i,a,x)$ is true? Intuitively, I feel that this condition is not decidable, i.e. there does not exist an algorithm to check this. Because if it is false then I would check each $x$ but never reach the end. Why do we allow this kind of undecidable property to be in our definition? I feel concerned about this because Turing machines are used in metamathematics, i.e. our reasoning about formal systems, and we want this reasoning to be finitary (whatever that means).
Long story short - if there is a partial function defined by undecidable property, how do I know whether for each specific value as an argument the function is defined or not. And can this create any problems?
logic turing-machines
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
$endgroup$
I am reading Kleene's "Mathematical Logic" $2002$ pp 242-246.
Let $T(i,a,x)$ stand for: $i$ is the index of a Turing machine (under particular enumeration) which when applied to $a$ as an argument will at moment $x$ (but not earlier) have completed the computation of a value (call that value $phi_i(a)$).
Then Kleene tells the theorem: (A) The predicate $T(i, a,x)$ is decidable. (B) $phi_i(a)$ as a partial function of $i$ and $a$ is computable.
I am not sure I understand the definition of a partial function. In the book, Kleene says that "As a function of $i$ and $a$ both, $phi_i (a)$ as we remarked is defined exactly when there exists $x$ such that $T(i,a,x)$ is true. So it is a partially defined number-theoretic function of two variables $i$ and $a$, or briefly a partial function."
My problem with this definition is that how do we know that there exists $x$ such that $T(i,a,x)$ is true? Intuitively, I feel that this condition is not decidable, i.e. there does not exist an algorithm to check this. Because if it is false then I would check each $x$ but never reach the end. Why do we allow this kind of undecidable property to be in our definition? I feel concerned about this because Turing machines are used in metamathematics, i.e. our reasoning about formal systems, and we want this reasoning to be finitary (whatever that means).
Long story short - if there is a partial function defined by undecidable property, how do I know whether for each specific value as an argument the function is defined or not. And can this create any problems?
logic turing-machines
logic turing-machines
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
asked Jan 8 at 5:37
Daniels KrimansDaniels Krimans
51239
51239
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
2
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
2
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06
|
show 4 more comments
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
2
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
2
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
2
2
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
2
2
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06
|
show 4 more comments
0
active
oldest
votes
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%2f3065836%2fdefinition-of-partial-function-using-predicate-that-is-possibly-undecidable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3065836%2fdefinition-of-partial-function-using-predicate-that-is-possibly-undecidable%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
$begingroup$
Yes, $exists x T(i,a,x)$ is undecidable. This is the halting problem. If all partial recursive functions had decidable domains, then there would hardly need to be a concept of a partial recursive function at all: you could just extend it with a default value to make it a total recursive function.
$endgroup$
– spaceisdarkgreen
Jan 8 at 5:56
$begingroup$
@spaceisdarkgreen thanks for comment, how does one make sense about part B of the theorem then? For example, what are the outputs for Turing machine of part B? I am not sure how it detects that function is not defined and what it outputs then.
$endgroup$
– Daniels Krimans
Jan 8 at 6:00
$begingroup$
It is a partial recursive function. The very idea of "partial" in partial recursive function is that on some inputs the algorithm does not terminate.
$endgroup$
– spaceisdarkgreen
Jan 8 at 6:12
2
$begingroup$
The key point in the definition of computable functions is the use of the $mu$-operator or unbounded search operator. The "unbounded" feaure is exactly what introduces the partial definiteness aspect.
$endgroup$
– Mauro ALLEGRANZA
Jan 8 at 12:18
2
$begingroup$
Close. The part about the Turing machine 'not knowing' is superfluous: it is not a thing that knows things, it is a thing that performs computations on inputs. You also need a provision that the machine does not halt when the function is undefined. Maybe it will be helpful to start with the Turing machine. Each Turing machine $T$ defines a partial function $f$ as follows: (1) If $T$ halts with value $v$ on input $x,$ then $f(x)=v.$ (2) If $T$ does not halt on input $x$ then $f(x)$ is undefined. A partial function is computable iff there is a Turing machine that defines it in this manner.
$endgroup$
– spaceisdarkgreen
Jan 9 at 1:06