Simulation of Turing machines by a regular rewrite rule

DOI10.1016/0304-3975(92)90022-8zbMath0753.68052OpenAlexW2024726864MaRDI QIDQ1199548

Max Dauchet

Publication date: 16 January 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90022-8

zbMATH Keywords

undecidabilityterminationinfinite rewriting

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42) Thue and Post systems, etc. (03D03)

Related Items (14)

On termination of one rule rewrite systems ⋮ Simple termination is difficult ⋮ Problems in rewriting III ⋮ Polynomials over the reals in proofs of termination : from theory to practice ⋮ An improved general path order ⋮ A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy ⋮ Simple termination of rewrite systems ⋮ Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming ⋮ On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting ⋮ Simple termination is difficult ⋮ Higher order unification via explicit substitutions ⋮ Relative undecidability in term rewriting. I: The termination hierarchy ⋮ Relative undecidability in term rewriting. II: The confluence hierarchy ⋮ Undecidable Properties on Length-Two String Rewriting Systems

Cites Work

• Unnamed Item
• Unnamed Item
• Weighted graphs: A tool for studying the halting problem and time complexity in term rewriting systems and logic programming
• Termination of rewriting
• Thue systems as rewriting systems
• Simulation of Turing machines by a left-linear rewrite rule

This page was built for publication: Simulation of Turing machines by a regular rewrite rule