STAT 2507 Study Guide - Final Guide: Turing Machine
23 Oct 2020
School
Department
Course
Professor
Document Summary
Read the definition of a 2dfa (two-headed finite automaton) given in problem 5. 26. Prove that p contains a language that is not recognizable by a 2dfa. It can be designed a turing machine and may be defined as: : on input, write 0 followed by in the tapes and halts. Thus, a mapping reduction of to or can be obtained . Now, a turing machine(tm) can be formed, which shows the functionality. : on input, write 1 followed by in the tapes and halts. Thus, a mapping reduction of to can be obtained . Therefore, the above explanation shows that contains a language which is not recognizable by a 2dfa . is non turing recognizable because is non turing recognizable. So, this allows that is non turing recognizable.
