0 votes 0 votes L={ <M> | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS } here what can we say about ‘L’? Theory of Computation theory-of-computation decidability + – newdreamz a1-z0 asked Dec 22, 2018 newdreamz a1-z0 483 views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Satbir commented Dec 22, 2018 reply Follow Share we can make a Turing machine to compute product of 2 numbers by converting numbers in binary format. L= i think it a language having encoding of <M> and since M will give the output for all (product of 2 numbers) so L should be decidable. 0 votes 0 votes Hemanth_13 commented Dec 22, 2018 reply Follow Share L is a set of TM's which computes the product of numbers, we can write different TM which can multiply single digit, two digits,3 digits,.... so the no of TM will be infinite. If we give someother TM and ask it perform multiplication it may or maynot halt i feel its Undecidable? 0 votes 0 votes newdreamz a1-z0 commented Dec 22, 2018 reply Follow Share https://gateoverflow.in/89091/turing-machine-computes-product-numbers-decidable-undecidable https://gateoverflow.in/84835/gate1990-3-vii#c140267 there are 2 derivations 0 votes 0 votes Satbir commented Dec 22, 2018 i edited by Satbir Dec 22, 2018 reply Follow Share what we have to check to see its decidable or not ? ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS here what does this line means ? a. product of any 2 no. b product of 2 specific numbes 0 votes 0 votes Manas Mishra commented Dec 22, 2018 reply Follow Share by rice 1st theorem as it is non monotonic property of Tm , so its undecidable 0 votes 0 votes Hemanth_13 commented Dec 22, 2018 reply Follow Share @Satbir if it is product of specific two numbers then L is finite right.. if we give some other TM (which is not in L) and asking it compute the product of those two number may or maynot halt right.. In that case as well its undecidable 1 votes 1 votes Manas Mishra commented Dec 22, 2018 reply Follow Share @Hemanth_13 cant we say that as it is non monotonic property so undecidable ? 0 votes 0 votes Ram Swaroop commented Dec 22, 2018 reply Follow Share Because behavior of machine is given 0 votes 0 votes Please log in or register to add a comment.