Turing machine

danh từ (noun)

Nghĩa chính

Máy tính trừu tượng có số lượng hữu hạn các trạng thái bên trong có thể có và hoạt động trên một băng bộ nhớ vô hạn bằng cách trước tiên đọc một ký hiệu từ một ô trong băng, sau đó, một cách xác định, dựa trên ký hiệu đó và trạng thái của máy, viết một ký hiệu vào ô đó, di chuyển đến một ô lân cận và/hoặc thay đổi trạng tháidanh từAn abstract computing machine that has a finite number of possible internal states and operates on an infinite memory tape by first reading a symbol from a cell in the tape, and then, deterministically, based on that symbol and the machine’s state, writing a symbol in that cell, moving to a neighboring cell, and/or changing state.

theo quy tắc (regular)

Cụm từ	Từ loại	Nghĩa
universal Turing machinedanh từ	danh từ	Máy Turing có khả năng mô phỏng hành vi của bất kỳ máy Turing nào
alternating Turing machinedanh từ	danh từ	Máy Turing không xác định chứa một quy tắc chấp nhận các phép tính tổng quát hóa các quy tắc được sử dụng trong định nghĩa các lớp phức tạp NP và co-NP
deterministic Turing machinedanh từ	danh từ	Máy Turing có các quy tắc quản lý chỉ xác định một hành động có thể thực hiện được đối với bất kỳ sự kết hợp nào giữa trạng thái của máy và ký hiệu đang được đọc
nondeterministic Turing machinedanh từ	danh từ	Biến thể của máy Turing có các quy tắc quản lý có thể chỉ định nhiều hơn một hành động có thể xảy ra đối với bất kỳ sự kết hợp nào giữa trạng thái của máy và ký hiệu đang được đọc