199 views
0 votes
0 votes
A Turing machine can compute product of any two numbers, hence decidable problem

Turing machine can perform product of two numbers, then it is an undecidable problem

 

what is the meaning of computing and performing here???

1 Answer

1 votes
1 votes

We can design a TM which can calculate the product of two numbers.https://www.geeksforgeeks.org/turing-machine-for-multiplication/      So it is  Decidable.                                                                                                                                                    However given a TM and asking whether it can perform product of two numbers............We do not know its behavior So it is Undecidable

Related questions

0 votes
0 votes
0 answers
2
Mk Utkarsh asked Nov 23, 2018
400 views
$\text{L}_1 = \{\text{<M>}|\text{M is a TM and L(M) is infinite} \}$Not RE$\text{L}_2 = \{ \text{<M>} | \text{M is a TM and L(M) is countable} \}$and $\text{L}_3 = \{ \t...