Construction of a universal prefix-free Turing machine
$begingroup$
How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly exists $rho_f$ such that $U(rho_fx) = f(x)$ for any $x$.
I read the construction by Downey and Hirschfeldt, but I need a detailed construction, partly because I am unfamiliar with the convention in this field. For example, how can one construct a universal prefix-free TM from a (usual) universal TM?
Thank you for you help in this matter.
computability
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
$endgroup$
add a comment |
$begingroup$
How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly exists $rho_f$ such that $U(rho_fx) = f(x)$ for any $x$.
I read the construction by Downey and Hirschfeldt, but I need a detailed construction, partly because I am unfamiliar with the convention in this field. For example, how can one construct a universal prefix-free TM from a (usual) universal TM?
Thank you for you help in this matter.
computability
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
$endgroup$
$begingroup$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
1
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
1
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07
add a comment |
$begingroup$
How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly exists $rho_f$ such that $U(rho_fx) = f(x)$ for any $x$.
I read the construction by Downey and Hirschfeldt, but I need a detailed construction, partly because I am unfamiliar with the convention in this field. For example, how can one construct a universal prefix-free TM from a (usual) universal TM?
Thank you for you help in this matter.
computability
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
$endgroup$
How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly exists $rho_f$ such that $U(rho_fx) = f(x)$ for any $x$.
I read the construction by Downey and Hirschfeldt, but I need a detailed construction, partly because I am unfamiliar with the convention in this field. For example, how can one construct a universal prefix-free TM from a (usual) universal TM?
Thank you for you help in this matter.
computability
computability
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
edited Feb 20 '14 at 7:15
Pteromys
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
asked Dec 17 '13 at 13:54
PteromysPteromys
2,46121745
2,46121745
$begingroup$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
1
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
1
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07
add a comment |
$begingroup$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
1
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
1
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07
$begingroup$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
$begingroup$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
1
1
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
1
1
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Given input $rho x$, start by simulating $T_rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_rho$ on each of them for up to $n$ steps. If $T_rho$ halts on one of the $y$s in $le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_rho$ on $x$.
It's clear that this works just as a universal machine if $rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $rho x$ and $rho xw$ because if $T_rho(x)$ and $T_rho(xw)$ both halt, the one that does so last will diverge in the above procedure.
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
$endgroup$
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
add a comment |
$begingroup$
Here is another way.
Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.
Now, let $y$ be the empty string. Now perform the following algorithm:
- Enumerate the domain of $f$.
- If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
- If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.
If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
$endgroup$
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
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%2f610423%2fconstruction-of-a-universal-prefix-free-turing-machine%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
$begingroup$
Given input $rho x$, start by simulating $T_rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_rho$ on each of them for up to $n$ steps. If $T_rho$ halts on one of the $y$s in $le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_rho$ on $x$.
It's clear that this works just as a universal machine if $rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $rho x$ and $rho xw$ because if $T_rho(x)$ and $T_rho(xw)$ both halt, the one that does so last will diverge in the above procedure.
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
$endgroup$
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
add a comment |
$begingroup$
Given input $rho x$, start by simulating $T_rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_rho$ on each of them for up to $n$ steps. If $T_rho$ halts on one of the $y$s in $le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_rho$ on $x$.
It's clear that this works just as a universal machine if $rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $rho x$ and $rho xw$ because if $T_rho(x)$ and $T_rho(xw)$ both halt, the one that does so last will diverge in the above procedure.
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
$endgroup$
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
add a comment |
$begingroup$
Given input $rho x$, start by simulating $T_rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_rho$ on each of them for up to $n$ steps. If $T_rho$ halts on one of the $y$s in $le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_rho$ on $x$.
It's clear that this works just as a universal machine if $rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $rho x$ and $rho xw$ because if $T_rho(x)$ and $T_rho(xw)$ both halt, the one that does so last will diverge in the above procedure.
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
$endgroup$
Given input $rho x$, start by simulating $T_rho$ on input $x$ until it halts, counting steps. (If it doesn't halt, then just diverge).
Let $n$ be the number of steps it takes for $T_rho$ to halt on $x$.
Now enumerate all strings $y$ that are either prefixes of $x$ or have $x$ as a prefix and are at most $n$ symbols long. (There are finitely many such $y$s of course). Simulate $T_rho$ on each of them for up to $n$ steps. If $T_rho$ halts on one of the $y$s in $le n$ steps, then diverge!
If none of the $y$s halt within the time limit, then halt with the output of $T_rho$ on $x$.
It's clear that this works just as a universal machine if $rho$ is actually a description of a prefix-free machine. On the other hand, the process is prefix-free by construction: it cannot halt on both $rho x$ and $rho xw$ because if $T_rho(x)$ and $T_rho(xw)$ both halt, the one that does so last will diverge in the above procedure.
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
answered Dec 17 '13 at 15:05
Henning MakholmHenning Makholm
243k17309554
243k17309554
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
add a comment |
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
Given $px$, how do you figure out what $p$ is?
$endgroup$
– PyRulez
Dec 13 '18 at 20:15
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
$begingroup$
@PyRulez: I'm assuming we're using a scheme for encoding Turing machines as symbol strings which is self-delimiting such that this is a trivial task. It is easy to see that such schemes exist (if everything else fails, take your favorite scheme and prepend a length in unary to every machine description -- as you do in your answer!). And the way the problem is set we only need to construct $U$ for one particular encoding of our own choice.
$endgroup$
– Henning Makholm
Dec 13 '18 at 23:54
add a comment |
$begingroup$
Here is another way.
Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.
Now, let $y$ be the empty string. Now perform the following algorithm:
- Enumerate the domain of $f$.
- If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
- If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.
If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
$endgroup$
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
add a comment |
$begingroup$
Here is another way.
Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.
Now, let $y$ be the empty string. Now perform the following algorithm:
- Enumerate the domain of $f$.
- If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
- If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.
If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
$endgroup$
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
add a comment |
$begingroup$
Here is another way.
Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.
Now, let $y$ be the empty string. Now perform the following algorithm:
- Enumerate the domain of $f$.
- If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
- If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.
If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
$endgroup$
Here is another way.
Let $p_f$ be a computable prefix code for partial recursive functions. For example, you could let $p_f$ be $0^{|d(f)|}1d(f)$, where $d(f)$ is a description of a turing machine computing $f$. Then given $p_fx$, we can compute $p_f$ and $x$.
Now, let $y$ be the empty string. Now perform the following algorithm:
- Enumerate the domain of $f$.
- If $y$ is enumerated, check if $x$ is empty. If it is, output $f(y)$. Otherwise, reject (or diverge).
- If $s$ is enumerated, where $y$ is a prefix of $s$, remove a symbol from the beginning of $x$ and add it to the end of $y$, and go back to step 1.
If $f$'s domain is prefix free, then $U(p_fx)$ will compute $f(x)$ if $x$ is in $f$'s domain, and otherwise diverge (which is fine). If $f$'s domain is not prefix free, $U(p_fx)$ will do something else. Either way, $U$ will have a prefix free domain.
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
answered Dec 13 '18 at 20:27
PyRulezPyRulez
5,00722471
5,00722471
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
add a comment |
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
$begingroup$
What happens in the second bullet if $x$ is already empty? If you reject in that case I think you reach the same restriction of $f$ as I do in my construction, assuming the enumeration is in order of increasing computation length.
$endgroup$
– Henning Makholm
Dec 14 '18 at 0:11
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%2f610423%2fconstruction-of-a-universal-prefix-free-turing-machine%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$
What does "prefix-free" mean in this context? Does "a TM whose domain is prefix-free" mean that if $U$ terminates on $rho x$ then it has to diverge on $rho xw$ if $w$ is nonempty, no matter what $rho$ is?
$endgroup$
– Henning Makholm
Dec 17 '13 at 13:56
1
$begingroup$
@HenningMakholm The answer to your second question is "Yes."
$endgroup$
– Pteromys
Dec 17 '13 at 14:46
1
$begingroup$
@Henning: this is a standard concept in Kolmogorov complexity. A language is prefix free if it contains no pair of strings one of which is a proper prefix of the other; a machine is prefix free if the language it accepts is prefix free.
$endgroup$
– Carl Mummert
Dec 18 '13 at 22:07