Log In
1 vote

1. given any two specific numbers

2. any two arbitrary numbers
in Theory of Computation 1.4k views

2 Answers

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..

thanks, got it

I think it is undecidable problem. You can check here.
Because the question is not asking there exist a TM which can do the product of two numbers. Instead, it is asking given any arbitrary TM, does it computes the product of two numbers.

i agree with you, may be turing machine doesnt halt on given input, so how can we say that it will compute product pf two numbers..
It must be undecidable for a given truing machine. But the explanation is very elaborate. Thank you!

It must be undecidable for a given truing machine

How ?? I think it is decidable.


@kumar.dilip Because you can convert it to halting problem maybe? Also why should it be decidable?


As we know according to the Turing thesis.

Any computation that can be done by the mechanical means can be performed by some Turing.

As we know we can perform the Multiplications from it. there exist an Algorithm for it.

What you are saying is right, but its not about the existence, suppose you are given an arbitrary TM and you would like to check if it is computing product of two numbers. Now you give the input and the machine is computing and it could be in loop or something and it is taking some time, now you cannot declare that this TM is not going to compute the product of the numbers since it did not halt, and nor can you declare that it will compute the product at this point of time. Its like halting problem or is it not?
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. ]

Related questions

1 vote
4 answers
A = { (M, w) | M is a TM that on input w, tries to move its head past the left end of the input } B = { (M, w) | M is a TM that on input w, moves its head left at least once, at some point} how to decide that a problem is decidable or undecidable , recognisable or unrecognisable ??
asked Apr 16, 2017 in Theory of Computation student2018 701 views
7 votes
0 answers
I am more interested to know which problems are Recursive Enumerable and which are Non Recursive Enumerable.
asked Sep 9, 2017 in Theory of Computation Manu Thakur 304 views
1 vote
1 answer
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?
asked Sep 13, 2017 in Theory of Computation adwaitLP 619 views
4 votes
2 answers
Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?
asked Jan 18, 2018 in Theory of Computation nikhil_cs 752 views