 |  Turing Machines 20 Flashcards |  Start |
 | What is the primary function of a Turing machine? |  Card: 1 / 20 |
| To recognize or decide languages based on given inputs. | Card: 2 / 20 |
| Fill in the blank: A Turing machine is formally defined as TM = (Q, ∑, Γ, δ, q0, #, h) where Q is a set of ______. | Card: 3 / 20 |
| States | Card: 4 / 20 |
| True or False: A Turing machine can only accept or reject an input string. | Card: 5 / 20 |
| False. A Turing machine can also run indefinitely without halting. | Card: 6 / 20 |
| Which of the following is NOT a component of a Turing machine? A) Tape B) Head C) Processor D) Finite control | Card: 7 / 20 |
| C) Processor | Card: 8 / 20 |
| Riddle: I can compute functions, yet I have no physical form, and I can loop without end. What am I? | Card: 9 / 20 |
| Turing machine | Card: 10 / 20 |
|  Unlock all Flashcards with EduRev Infinity Plan Starting from @ ₹99 only | |
| Fill in the blank: A language L is said to be ______ if there exists a Turing machine that halts in an accepting state for every string in L. | Card: 11 / 20 |
| Decidable | Card: 12 / 20 |
| True or False: The halting problem is decidable for all Turing machines. | Card: 13 / 20 |
| False. The halting problem is undecidable. | Card: 14 / 20 |
| What is the significance of the Church-Turing thesis? | Card: 15 / 20 |
| It states that any mechanical computation can be performed by a Turing machine. | Card: 16 / 20 |
| Which type of Turing machine has an infinite tape on both sides? | Card: 17 / 20 |
| Two-way infinite Turing machine | Card: 18 / 20 |
| Riddle: I am a problem with no solution, where no Turing machine can decide my fate. What am I? | Card: 19 / 20 |
| Halting problem | Card: 20 / 20 |
| Completed! Keep practicing to master all of them. |  Restart |
