Which formal computational model defines the boundary of what is algorithmically computable according to the Church-Turing Thesis?
The Church-Turing Thesis posits that any problem solvable by an intuitive algorithm can be computed by a Turing Machine.
[BPSC TRE 2.0 Class 11-12 PYQ] What is the difference between a Decider (Halting TM) and a general Turing Machine?
Statements (A), (B), and (C) are all true: Deciders always halt on all inputs, recognizing Recursive (Decidable) languages.
Which language class corresponds to Type-0 in the Chomsky Hierarchy?
Type-0 languages are Recursively Enumerable languages, generated by Unrestricted Grammars and recognized by Turing Machines.
What type of grammar generates Context-Sensitive Languages (Type-1)?
Type-1 Context-Sensitive Grammars require non-contracting production rules |$\alpha | <= |\beta |$ and correspond to Linear Bounded Automata (LBA).
The Halting Problem for Turing Machines is:
Alan Turing proved in 1936 that the Halting Problem is Undecidable. However, it is Recursively Enumerable (a Universal TM can simulate and halt if it accepts).