EECS 2001 Lecture 9: TM_comp_of_funct

• School: York University
• Department: Electrical Engineering and Computer Science
• Course: EECS 2001
• Professor: Eric Ruppert

Document Summary

Example: design a tm m to compute the absolute value |n m|. One of the tm"s to solve this problem works as follows. Given an input repre- sentation 0n10m of the input (n, m), m will be matching pairs of 0"s on both sides of the separating 1. It will halt when such matching is no longer possible. M =< q, , , q0, , > where: Q = {q0, q1, q2, ql, qr, qf } = {0, 1, b, x} and the transition function is given by this table q0 qr q1 ql q2 qf. 0 (qr, x, r) (qr, 0, r) (ql, x, l) (q2, 0, l) 1 (qf , 1, ) (q1, 1, r) (q2, 1, l) X (q1, x, r) (q1, x, l) (q0, x, r) In q0, m tries to locate the rst 0 in the rst argument and, if there are none,