3,580 views

3 Answers

3 votes
3 votes

If we can have Turing enumerator which can generate strings in lexicographic order , then the set is known as recusive(decidable) one else if order is not maintained but Turing enumeration is possible then it is recursively enumerable..

So in this case the problem is to compute the product of two numbers ..So we can enumerate the results in sequence and hence let Turing enumerator enumerates the string in ordered (lexicographic) manner as every number can be written in the form of product of 2 numbers..

U can also understand like this :

A problem is said to be decidable iff we have an algorithm for it..So for multiplication trivially we have algorithm which can be implemented in a computer..

So equivalently we can also have Halting Turing Machine for this purpose..Hence it is a recursive(decidable) set..

2 votes
2 votes
A Turing machine can compute product of any two numbers, hence decidable problem. However, if the question is asked to find out whether a given Turing machine can perform product of two numbers, then it is an undecidable problem
[ Proof: design a (halting) Turing machine which can compute product of two number (recursive & decidable). Now give the same input to the given Turing machine and compare the output with your TM's output. If you can enumerate this to all the natural number then you can say the given TM can perform the product of two number. Since the given TM is unknown to us, it could be possible that for any two number given as a input to the TM might cause it to loop infinitely and it might never halt (halting problem). If that happens, then the entire problem of whether a particular TM can perform product of two numbers will become undecidable. ]
0 votes
0 votes

There is no specific algorithm (as per church-turing thesis) or turing machine that will compute the multiplication of two numbers only. But in general it can compute the multiplication of any two numbers taken. Hence 1) undecidable

and   2) decidable

Related questions

2 votes
2 votes
1 answer
2
adwaitLP asked Sep 13, 2017
2,099 views
If M is a turing machine and Language accepted by that turning machine is L(M) such that L is regular language. Whether this Statement is decidable or undecidable?