In English, explain and contrast the terms “recognize” and “decide” as they relate to Turing Machines.
Recognize
Recognize in the Turing machine is for recpgnizing or identifing the language.
A turing machine recognises the language ,if it halts and accepts all strings in language
Decide
Decide in the Turing machine is for deciding the language
Turing machine decides the language if it halts and accepts on all strings in that language.
And it halts and rejects if it is not in that language
contrastion between Recognise and Decide
*Decider also halts if string is not in language
*But recognizer may halt or maynot halt halt in the string that are not in the language
*On all the inputs decider should halt either in accept or reject state
*On all inputs recognizer may or may not halt on strings that are not in language
Get Answers For Free
Most questions answered within 1 hours.