Btap turing lý thuyết độ phức tạp tính toán (KMA)
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (176.98 KB, 12 trang )
<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">
<b>Câu 1. Xây dựng máy Turing 1 băng đốn nhận ngơn ngữ { 0i1j với điều kiện nào đó của i, j, ví dụ i>j, i<j, i=j+1,j=i+1, i=j-1, i=j+2}</b>
Máy Turing 1 băng đốn nhận ngơn ngữ {0i1j với ...} được xác định như sau: M = {Q, {0,1}, {0,1,Ø}, 𝛿, q0, qy, qn } Trong đó: Q = {q0, q0’, q1, q2, q3, q4, ..., qy, qn}
Hàm chuyển được xác định như sau:
<b>Điều kiện: i<j</b>
</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4"><b>Câu 2. Xây dựng máy Turing 1 băng tính hàm f(n,m) = </b>
</div>
