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