We know all computer computable problems can be solved using the infinite tape and finite control system of the turing machine. Now think something different, let the tape is finite but the control system is infinite. Now can we solve the same set of problems with this machines?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Assuming the tape is always made long enough to hold the input, then infinite control allows you to decide any language at all. The infinite control can just contain one state for each possible string that's been read so far. When it reaches the end of the input, it can accept or reject as appropriate.
answered Jan 15, 2019 at 13:36