{"corpus_id":17419147,"paper_sha":"a74f665078a77a144d5d7035a9a22ebea3c08398","doi":"10.4204/EPTCS.166.4","arxiv_id":"1404.0545","pmid":null,"pmcid":null,"mag_id":2954386378,"dblp_id":"journals/corr/Given-Wilson14","acl_id":null,"title":"An Intensional Concurrent Faithful Encoding of Turing Machines","year":2014,"publication_date":"2014-04-02","venue":"International Conference on Information and Computation Economies","journal":{"name":null,"pages":"21-37","volume":null},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Computer Science"],"reference_count":37,"citation_count":10,"influential_citation_count":0,"is_open_access":true,"arxiv_categories":["cs.FL"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":"EPTCS 166, 2014, pp. 21-37","mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://arxiv.org/pdf/1404.0545","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/a74f665078a77a144d5d7035a9a22ebea3c08398","s2_open_access_license":"CCBYNCND","s2_open_access_status":"GOLD","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"The benchmark for computation is typically given as Turing computability; the ability for a computation to be performed by a Turing Machine. Many languages exploit (indirect) encodings of Turing Machines to demonstrate their ability to support arbitrary computation. However, these encodings are usually by simulating the entire Turing Machine within the language, or by encoding a language that does an encoding or simulation itself. This second category is typical for process calculi that show an encoding of lambda-calculus (often with restrictions) that in turn simulates a Turing Machine. Such approaches lead to indirect encodings of Turing Machines that are complex, unclear, and only weakly equivalent after computation. This paper presents an approach to encoding Turing Machines into intensional process calculi that is faithful, reduction preserving, and structurally equivalent. The encoding is demonstrated in a simple asymmetric concurrent pattern calculus before generalised to simplify infinite terms, and to show encodings into Concurrent Pattern Calculus and Psi Calculi.","claims":[{"public_id":"cl_b1dd132e6a92b330f128e76861bf26ea","status":"active","text":"The encoding is demonstrated in a simple asymmetric concurrent pattern calculus before being generalised to simplify infinite terms.","confidence":0.9,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/claims/cl_b1dd132e6a92b330f128e76861bf26ea"},{"public_id":"cl_79e840d302e9a17fbb3c8b38dfb47a94","status":"active","text":"The encoding is shown to work in Concurrent Pattern Calculus and Psi Calculi.","confidence":0.85,"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/claims/cl_79e840d302e9a17fbb3c8b38dfb47a94"}],"concepts":[{"public_id":"co_139466e075c9029e71a9ef6f67161a2f","status":"active","name":"infinite terms","description":"Terms that represent infinite computations or structures, simplified by the generalised encoding.","types":["concept","object"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_139466e075c9029e71a9ef6f67161a2f"},{"public_id":"co_240482c36da87f88a054a7b75a8728e6","status":"active","name":"intensional process calculi","description":"Process calculi that focus on the structure of processes rather than their extensional behavior.","types":["framework","theory"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_240482c36da87f88a054a7b75a8728e6"},{"public_id":"co_4a41c2c0e6effa3336eba76a4c854af9","status":"active","name":"asymmetric concurrent pattern calculus","description":"A simple pattern calculus variant used to demonstrate the initial encoding of Turing Machines.","types":["calculus","method"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_4a41c2c0e6effa3336eba76a4c854af9"},{"public_id":"co_533d0b632ec89f8db6628a4f82b097e2","status":"active","name":"Turing Machines","description":"The classical model of computation used as a benchmark for computational completeness.","types":["model","standard"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_533d0b632ec89f8db6628a4f82b097e2"},{"public_id":"co_5a8d964481d63fd00379d27c17c81c5f","status":"active","name":"faithful encoding","description":"An encoding of Turing Machines into process calculi that preserves reduction steps and structural equivalence.","types":["method","property"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_5a8d964481d63fd00379d27c17c81c5f"},{"public_id":"co_7f25d8ddeec3df9e3f1f831c76f84441","status":"active","name":"Concurrent Pattern Calculus","description":"A process calculus that supports pattern matching and concurrency, into which the encoding is shown.","types":["calculus","framework"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_7f25d8ddeec3df9e3f1f831c76f84441"},{"public_id":"co_820553c62d4c3f57d4a1212f5e8a3918","status":"active","name":"Psi Calculi","description":"A family of process calculi with explicit data structures, into which the encoding is shown.","types":["calculus","framework"],"aliases":[],"contributors":[{"id":32,"public_id":"7c402c1b98","public_label":"뀨 (7c402c1b98)","roles":["extraction"],"url":"https://sah.borca.ai/u/7c402c1b98"},{"id":17,"public_id":"322360f1c1","public_label":"Killer Whale (322360f1c1)","roles":["review"],"url":"https://sah.borca.ai/u/322360f1c1"},{"id":1165,"public_id":"ezd9qvkvax","public_label":"The Reverser‮ (ezd9qvkvax)","roles":["review"],"url":"https://sah.borca.ai/u/ezd9qvkvax"}],"url":"https://sah.borca.ai/concepts/co_820553c62d4c3f57d4a1212f5e8a3918"}],"external_ids":{"DOI":"10.4204/EPTCS.166.4","ArXiv":"1404.0545","PubMed":null,"PubMedCentral":null,"MAG":2954386378,"DBLP":"journals/corr/Given-Wilson14","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/1404.0545","landing_url":"https://www.semanticscholar.org/paper/a74f665078a77a144d5d7035a9a22ebea3c08398","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":"CCBYNCND","status":"GOLD","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":634567,"paper_uid":"0e4360d0-51f2-4160-bf42-c9e9b9f2d8b6","canonical_identity":{"paper_id":634567,"paper_uid":"0e4360d0-51f2-4160-bf42-c9e9b9f2d8b6","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/17419147"}