= Solution
\b[$\mathcal L_{\ell3}$ is <undecidable>.] The condition depends only on the accepted <formal language>. It holds for a <Turing machine> accepting the <empty language>, and fails for a <Turing machine> accepting the singleton $\{aaaa\}$, where $a$ is an <alphabet> symbol. It is therefore a nontrivial <extensional property of programs>, and <Rice's theorem> applies. In particular, the condition does not assert that the machine halts on every <input>; nonacceptance of long <words over an alphabet> may result from rejection or from an infinite computation.
\b[$\mathcal L_{1\mathrm T}$ is a <decidable language>: it consists of every valid <Turing machine encoding>.] Every <multitape Turing machine> has an equivalent <single-tape Turing machine>. To see this, represent the finitely used portions of its tapes on one tape, separated by delimiters, and mark each simulated head position. To simulate one step, scan these portions to read the marked symbols, retain this fixed number of symbols and the control state in finite control, and scan again to update the symbols and head marks. Extend a represented portion with a blank cell when necessary. Each simulated step takes finitely many real steps.
The <single-tape Turing machine> accepts exactly when the simulated <multitape Turing machine> accepts; infinite computations remain infinite. The simulation may increase <time complexity>, but the question only asks about accepted <formal languages>. Hence a decider simply checks the syntax of the <Turing machine encoding> and accepts every valid description. <Rice's theorem> does not make this property <undecidable>, because the property is true of every <computably enumerable language> and is therefore trivial in the theorem's sense.
$$
\boxed{\mathcal L_{\ell3}\text{ is undecidable};\qquad\mathcal L_{1\mathrm T}\text{ is decidable}.}
$$
Back to article page
