FLA-Unit quiz

Which of the following are the models equivalent to Turing machine?

• Multi tape turing machine

• Multi track turing machine

• Register machine

• All of the mentioned

What is the primary purpose of a Turing Machine in theoretical computer science?

• To perform basic arithmetic

• To model the capabilities and limitations of computation

• To create computer hardware

• To develop artificial intelligence

Which type of language can a Turing Machine recognize?

• Regular language

• Context-free language

• Context-sensitive language

• Recursively enumerable language

A language is considered Turing-decidable if:

• A Turing Machine can halt and accept all strings in the language

• A Turing Machine can process only some inputs in the language

• The language can only be processed by finite automata

• A Turing Machine processes it with probabilistic outcomes

Which of the following is a limitation of Turing Machines?

• They can only process binary input

• They are slower than real computers

• They cannot solve all computational problems

• They have finite memory

Which of the following is an undecidable problem related to Turing Machines?

• Finding the sum of two numbers

• Multiplying two matrices

• The Halting Problem

• Checking for prime numbers

The Halting Problem is undecidable because:

• There is no algorithm to determine if a Turing Machine halts for every input

• Turing Machines do not halt

• It requires infinite time to solve

• There is no Turing Machine capable of performing arithmetic calculations

Which of the following statements about undecidable problems is TRUE?

• All problems with algorithms are undecidable

• No Turing Machine can decide an undecidable problem

• All mathematical problems are undecidable

• There exists at least one algorithm for every undecidable problem

Which of these problems is known to be undecidable?

• Determining if a given number is prime

• Determining if a context-free language is empty

• Determining if two context-free grammars are equivalent

• Calculating the shortest path in a graph

What is meant by a 'recursively enumerable' language in the context of undecidability?

• A language that a Turing Machine can recognize and decide

• A language for which a Turing Machine can recognize members but may not halt for non-members

• A language that can be processed only by finite automata

• A language with a regular grammar