himoundary
asked on
Theory of computation: computable/non computable problems - does a string x belong to a langage L?
This is a question about the theory of computation.
While I understand that EE probably does not cater to such questions, I will still post it here cos EE has been one of my favorite places to seek online answers to my questions.
The question:
Solving any computational problem can be reduced to/expressed as answering the question "does the string x belong to the language L"? where x and L can be described as required.
(have I written the above accurately?)
I can understand how this applies to a lot of computational problems.
I want to know how this would apply to the following computable problem of the following kind
2*3 = ?
While I understand that EE probably does not cater to such questions, I will still post it here cos EE has been one of my favorite places to seek online answers to my questions.
The question:
Solving any computational problem can be reduced to/expressed as answering the question "does the string x belong to the language L"? where x and L can be described as required.
(have I written the above accurately?)
I can understand how this applies to a lot of computational problems.
I want to know how this would apply to the following computable problem of the following kind
2*3 = ?
This question probably belongs in
http:/Programming/Theory/
http:/Programming/Theory/
ASKER
equals ::= three three
three ::= "xxx"
What does this mean? (am assuming ::= is the assignment operator)
(my question is about strings and languages)
three ::= "xxx"
What does this mean? (am assuming ::= is the assignment operator)
(my question is about strings and languages)
It's a BNF description of a language that accepts two strings of three x's each
the number of x's in a string that belongs to that language is the answer to
2*3 = ?
http://en.wikipedia.org/wiki/Backus-Naur_form
the number of x's in a string that belongs to that language is the answer to
2*3 = ?
http://en.wikipedia.org/wiki/Backus-Naur_form
ASKER
@ ozo
Can you please clarify further?
I want to compute a*b.
This is obviously computable by a Turing machine and hence I should be able to get the answer by asking the question whether x belongs to L (where I may define how I construct x, L and how I interpret the boolean response - belongs/doesn't belong).
Can you please specify the following (in terms of a, b if required)
1) The language L (or ignore this if you've already specified L in the previous post).
2) The string x.
3) How to interpret the response belongs/doesn't belong to get the result
Thanks!
Can you please clarify further?
I want to compute a*b.
This is obviously computable by a Turing machine and hence I should be able to get the answer by asking the question whether x belongs to L (where I may define how I construct x, L and how I interpret the boolean response - belongs/doesn't belong).
Can you please specify the following (in terms of a, b if required)
1) The language L (or ignore this if you've already specified L in the previous post).
2) The string x.
3) How to interpret the response belongs/doesn't belong to get the result
Thanks!
S -> 0=
0 -> 0b
0 -> *1
1b -> b1c
cb -> bc
c= -> =c
1= -> 2=
b2 -> 2b
*2 -> a*1
*1 -> *
should accept strings of the form
aa*bbb=cccccc
where the number of a's multiplied by the number of b's equals the number of c's
(If that's what the question was asking, I think it should be worth more than 50 points)
0 -> 0b
0 -> *1
1b -> b1c
cb -> bc
c= -> =c
1= -> 2=
b2 -> 2b
*2 -> a*1
*1 -> *
should accept strings of the form
aa*bbb=cccccc
where the number of a's multiplied by the number of b's equals the number of c's
(If that's what the question was asking, I think it should be worth more than 50 points)
ASKER
Ozo, you just don't seem to be getting my question. Or perhaps I am not smart enough to figure out how your post answers my question.
I should point out a minor correction in your post, as well. instead of "should _accept_ strings of the form", it should be "should _generate_ all strings of the form"
(assuming the you've worked it out correctly.
However, that was besides the point. The point is that I am asking my question in the context of the following statement: (which is in my first post):
"Solving any computable problem can be reduced to answering the question 'does the string x belong to the language L?' where x and L can be described as required."
Do you understand this statement?
If yes, then we can go further.
My question is this statement valid for all computable problems. If so, how is this valid for problems of the type a*b=? (which are obviously computable). Let me emphasize, I don't care about the "multiplication" part of it. I could just as well be: a+b=?
Now, read my previous post containing points 1), 2) and 3).
You don't need to provide the specification to generate strings of the from aa*bbb=ccc (or 2*3=6). If you think such a language would be useful/required, you could just say that there is a language L such that it has all strings of the from a*b=c for all values of a, b belonging to the set N, natural numbers (say). [Note here that this will be a _countably_ infinite set as the set N*N is countably infinite.]
Ozo, you seem to be good at coming up with specifications of languages, but I don't think it will be required. So post further only if you think you understand exactly what I am asking.
(Of course, please feel free to ask me to clarify any part of my question that you think is not clear.)
I should point out a minor correction in your post, as well. instead of "should _accept_ strings of the form", it should be "should _generate_ all strings of the form"
(assuming the you've worked it out correctly.
However, that was besides the point. The point is that I am asking my question in the context of the following statement: (which is in my first post):
"Solving any computable problem can be reduced to answering the question 'does the string x belong to the language L?' where x and L can be described as required."
Do you understand this statement?
If yes, then we can go further.
My question is this statement valid for all computable problems. If so, how is this valid for problems of the type a*b=? (which are obviously computable). Let me emphasize, I don't care about the "multiplication" part of it. I could just as well be: a+b=?
Now, read my previous post containing points 1), 2) and 3).
You don't need to provide the specification to generate strings of the from aa*bbb=ccc (or 2*3=6). If you think such a language would be useful/required, you could just say that there is a language L such that it has all strings of the from a*b=c for all values of a, b belonging to the set N, natural numbers (say). [Note here that this will be a _countably_ infinite set as the set N*N is countably infinite.]
Ozo, you seem to be good at coming up with specifications of languages, but I don't think it will be required. So post further only if you think you understand exactly what I am asking.
(Of course, please feel free to ask me to clarify any part of my question that you think is not clear.)
ASKER
okay. i read that. helped recap what i had studied in the course on "models of computation", but couldn't see how that helps the question i've posed.
first, just tell me is the following statement strictly true or not:
"Solving any computable problem can be reduced to answering the question 'does the string x belong to the language L?' where x and L can be described as required."
first, just tell me is the following statement strictly true or not:
"Solving any computable problem can be reduced to answering the question 'does the string x belong to the language L?' where x and L can be described as required."
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
ok. in that case, suppose i have the following:
L =
{ 1*1=1, 1*2=2,...
2*1=2, 2*2=4...
3*1=3, 3*2=6..
:
}
(these are strings in the language L) (Note that this set will be countable as I can always reach the string corresponding to a*b for any a,b in a finite number of steps by traversing diagonally etc...)
I now need to find out the value of 34*56.
So I keep on asking if the following strings belong to L :
34*56=1, 34*56=2, 34*56=3.... till I get an answer in the affirmative.
Is this the way to do it? And since we can always do something like this (at least in theory), is that why we say that the model of "strings-languages-languag
L =
{ 1*1=1, 1*2=2,...
2*1=2, 2*2=4...
3*1=3, 3*2=6..
:
}
(these are strings in the language L) (Note that this set will be countable as I can always reach the string corresponding to a*b for any a,b in a finite number of steps by traversing diagonally etc...)
I now need to find out the value of 34*56.
So I keep on asking if the following strings belong to L :
34*56=1, 34*56=2, 34*56=3.... till I get an answer in the affirmative.
Is this the way to do it? And since we can always do something like this (at least in theory), is that why we say that the model of "strings-languages-languag
that is a way to do it.
Another way, if you have an oracle for a language L' of strings that are prefixes of strings in language L might be to ask if
34*56=1 is in language L' and if it is, ask if 34*56=10 ... 34*56=19 are in language L'
then if 34*56=190 is in language L', etc.
Another way, if you have an oracle for a language L' of strings that are prefixes of strings in language L might be to ask if
34*56=1 is in language L' and if it is, ask if 34*56=10 ... 34*56=19 are in language L'
then if 34*56=190 is in language L', etc.
ASKER
Hey, thats an interesting way. Thanks.
But anyways, I was hoping that there would be a way to solve the problem by asking just one question and somehow interpreting the boolean answer; seems thats not going possible for such a problem.
(Btw, Can you provide any reference on the web or elsewhere which deals with the correspondence between solving computable problems and the whole using-a-machine-to-determi
Thanks!
But anyways, I was hoping that there would be a way to solve the problem by asking just one question and somehow interpreting the boolean answer; seems thats not going possible for such a problem.
(Btw, Can you provide any reference on the web or elsewhere which deals with the correspondence between solving computable problems and the whole using-a-machine-to-determi
Thanks!
three ::= "xxx"