Siêu đại diện có thể đại diện cho máy Turing không xác định không?

Question

Có ai biết về bất kỳ giấy tờ, văn bản, hoặc các tài liệu khác thảo luận bằng cách sử dụng một siêu đồ thị để thực hiện hoặc đại diện cho một máy Turing không xác định? Họ có thực tế tương đương không?

Tôi khá chắc chắn rằng một siêu đồ thị có thể đúng và hoàn toàn đại diện cho các chuyển đổi trạng thái trạng thái của một máy Turing không xác định, chẳng hạn. Nhưng tôi đã không thể tìm thấy bất cứ điều gì trong in ấn có thể xác minh điều này. Điều này dường như với tôi như một mối quan hệ rõ ràng như vậy, tuy nhiên thực tế là tôi không tìm thấy nghệ thuật trước đây làm cho tôi nghĩ rằng tôi đang đi sai đường. (Nó cũng có thể là trường hợp mà những gì tôi đang tìm kiếm chỉ là không thể truy cập đủ cho tôi để hiểu những gì nó nói.) ;-)

Tại sao tôi hỏi: Tôi đang làm việc trên một gói mã nguồn mở mà không lưu trữ dữ liệu phân tán và tính toán phân tán trong một mạng ngang hàng. Tôi đang tìm cấu trúc dữ liệu nguyên thủy nhất có thể hỗ trợ chức năng cần thiết. Cho đến nay, một siêu đồ thị phân tán trông đầy hứa hẹn. Lý do của tôi là, nếu một siêu đồ thị có thể hỗ trợ một cái gì đó chung chung như một máy Turing không xác định, thì nó sẽ có thể hỗ trợ một DSL Turing-complete cấp cao hơn. (Có nhiều lý do khác mà đoạn "không xác định" có thể có giá trị đối với tôi nữa, phải làm với việc kiểm soát phiên bản của dữ liệu phân tán và/hoặc kết quả tính toán. Cố gắng tránh một luận án ở đây)

Câu trả lời một phần:

• Các nhân viên opencog có một cuộc thảo luận chuyên sâu về cách đồ thị siêu khớp với các mô hình tính toán khác nhau; này dường như có liên quan đến sự phát triển của gói HypergraphDB: http://markmail.org/message/5oiv3qmoexvo4v5j
• Over trên MathOverflow, có một câu hỏi thảo luận về những gì hypergraphs thể làm - không đề cập đến Turing nào, nhưng tôi muốn thêm nó: https://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs
• Nếu một đồ thị có thể đại diện cho một máy Turing không xác định, thì tôi nghĩ rằng một đồ thị với các cạnh có trọng số sẽ tương đương với probabalistic máy Turing. http://en.wikipedia.org/wiki/Probabilistic_Turing_machine

Answer 1

Một hypergraph chỉ là một đồ thị G=(V,E) nơi V là tập hợp các đỉnh (nút) và E là một tập hợp con của Powerset của V. Nó là một cấu trúc dữ liệu.

Vì vậy, một đồ thị phổ biến chỉ là một đồ thị với thứ hạng 2. (nghĩa là mỗi bộ trong E chứa chính xác hai đỉnh). Một đồ thị siêu trực tiếp sử dụng các cặp (X,Y) làm các cạnh ở đó các số X và Y là các bộ.

Nếu bạn muốn lập mô hình máy turing thì bạn cần lập mô hình 'băng'. Bạn có muốn băng 'nhúng' trong biểu đồ không? Tôi nghĩ rằng bạn có thể có nhiều may mắn hơn suy nghĩ về luận án Church-Turing (Alonso Church, Lambda calculus). Phép tính Lambda là một dạng của hệ thống viết lại và chắc chắn có một chi nhánh sử dụng viết lại đồ thị (và hypergrpahs). Tất nhiên các quá trình chuyển đổi có thể được mô hình hóa như một đồ thị (tôi không chắc chắn những gì bạn có trong tâm trí, nhưng cách tiếp cận thẳng về phía trước không thực sự hữu ích) nếu bạn đã mô hình hóa bình thường bạn có thể sẽ tạo một từ điển/hashmap với tuples là các khóa (State, Symbol) và các giá trị đang được (State, Rewrite, Left | Right).ví dụ:

states = {1,2,3} 
symbols = {a,b,c} 
moves = L, R 
delta = { (1,a) -> (1,b,R) 
      (1,b) -> (2,c,L) 
      ... 
} 

vì vậy nếu bạn muốn đồ thị, trước tiên bạn cần V = trạng thái U ký hiệu U di chuyển. Rõ ràng họ cần phải được phân chia bộ. như {1, a} -> {1, b, R} là theo định nghĩa tương đương với {a, 1} -> {b, R, 1}, vv

states = {1,2,3} 
symbols = {a,b,c} 
moves = L, R 
V = {1,2,3,a,b,c,L,R} 
E = { ({1,a},{1,b,R}) 
     ({b,1},{L,2,c}) 
     ... 
} 
turing-hypergraph = (V,E) 

Như tôi đã đề cập trước đó, nhìn lập biểu đồ viết lại hoặc viết lại từ.