0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.