2011-09-10
HW1 Problem 1.10.
Originally Posted By: jnewth
I think I solved this one but it's a bit hand-wavey. What I wanted to show is that if a function f is in DTIME(T(n)) it means that there exists some TM capable of deciding the language in no more than c*T(n). By deciding, we mean that this TM halts on all inputs and accepts if the input is in the language.
First question: Can someone give me an intuitive understanding of what "being in the language" means in this case? Does that mean that programs that compute the function f are in the language, and programs that don't compute f are not in the language?
Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?
I figured a really simple way to do this would be to show how to actually construct the TM that could simulate a program written in the language.
Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps?
Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?
First question: Can someone give me an intuitive understanding of what "being in the language" means in this case? Does that mean that programs that compute the function f are in the language, and programs that don't compute f are not in the language?
Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?
I figured a really simple way to do this would be to show how to actually construct the TM that could simulate a program written in the language.
Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps?
Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?
'''Originally Posted By: jnewth'''
I think I solved this one but it's a bit hand-wavey. What I wanted to show is that if a function f is in DTIME(T(n)) it means that there exists some TM capable of deciding the language in no more than c*T(n). By deciding, we mean that this TM halts on all inputs and accepts if the input is in the language. <br><br>First question: Can someone give me an intuitive understanding of what "being in the language" means in this case? Does that mean that programs that compute the function f are in the language, and programs that don't compute f are not in the language? <br><br>Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?<br><br>I figured a really simple way to do this would be to show how to actually construct the TM that could simulate a program written in the language.<br><br>Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps? <br><br>Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?
First question: Can someone give me an intuitive understanding of what "being in the language" means in this case? Does that mean that programs that compute the function f are in the language, and programs that don't compute f are not in the language?
You are going to be simulating programs which compute boolean functions. i.e., on any input string they output 0 or 1. The language corresponding to such a function is just the collection of strings on which the output is 1.
Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?
The problem actually doesn't define what a step of such a program is. Assume it means execute one instructions.
So the question is asking to show that if in computing a boolean function f(x), a program executes T(|x|) instructions,
then there is a Turing machine computing the same functions which runs in time O(T(|x|). i.e., this shows f in DTIME(T(|x|)).
Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps?
That would give a quadratic simulation. You need to show you can simulate a program instruction in constantly many steps.
Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?
That depends on how you answer the question. My guess is yes.
You are going to be simulating programs which compute boolean functions. i.e., on any input string they output 0 or 1. The language corresponding to such a function is just the collection of strings on which the output is 1.
Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?
The problem actually doesn't define what a step of such a program is. Assume it means execute one instructions.
So the question is asking to show that if in computing a boolean function f(x), a program executes T(|x|) instructions,
then there is a Turing machine computing the same functions which runs in time O(T(|x|). i.e., this shows f in DTIME(T(|x|)).
Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps?
That would give a quadratic simulation. You need to show you can simulate a program instruction in constantly many steps.
Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?
That depends on how you answer the question. My guess is yes.
First question: Can someone give me an intuitive understanding of what "being in the language" means in this case? Does that mean that programs that compute the function f are in the language, and programs that don't compute f are not in the language?<br><br>You are going to be simulating programs which compute boolean functions. i.e., on any input string they output 0 or 1. The language corresponding to such a function is just the collection of strings on which the output is 1.<br><br><br>Second question: Does that make sense as an attack on this problem? Have I misunderstood the problem?<br><br>The problem actually doesn't define what a step of such a program is. Assume it means execute one instructions.<br>So the question is asking to show that if in computing a boolean function f(x), a program executes T(|x|) instructions,<br>then there is a Turing machine computing the same functions which runs in time O(T(|x|). i.e., this shows f in DTIME(T(|x|)).<br><br>Third question: Is there more to it than showing that a single step in this program can be simulated in no more than c*T(n) steps? <br><br>That would give a quadratic simulation. You need to show you can simulate a program instruction in constantly many steps.<br><br>Fourth question: Are there any steps in a direct simulation that would require than 1 step per 1 language step?<br>That depends on how you answer the question. My guess is yes.
(c) 2024 Yioop - PHP Search Engine