Một enumerator (máy liệt kê) là biến thể của máy Turing sinh ra lần lượt các chuỗi của một ngôn ngữ. Một ngôn ngữ là Turing-recognizable khi và chỉ khi có enumerator liệt kê nó.
Xét enumerator liệt kê mọi chuỗi trên bảng chữ {0, 1} theo thứ tự chuẩn (shortlex): ngắn trước dài sau, cùng độ dài thì theo thứ tự từ điển (0 < 1).
Thứ tự: ε, 0, 1, 00, 01, 10, 11, 000, …
Cho k, hãy in ra chuỗi thứ k (đánh số từ 1). Chuỗi rỗng ε được in là e.
Ví dụ: k = 1 → e; k = 2 → 0; k = 4 → 00.
Một số nguyên k (đánh số từ 1).
1 ≤ k ≤ 1000000000.
Chuỗi thứ k theo thứ tự shortlex; chuỗi rỗng in là e.
Ví dụ:
Đầu vào:
1
Đầu ra:
e
Giải thích:
Đang tải editor...