Minsky Machines and Algorithmic Problems

DOI10.1007/978-3-319-23534-9_17zbMath1465.03077arXiv1504.07736OpenAlexW834129998MaRDI QIDQ2947180

Mark V. Sapir

Publication date: 22 September 2015

Published in: Fields of Logic and Computation II (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.07736

zbMATH Keywords

semigroupword problemvarietygroupidentityMinsky machinesuniform word problem

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40) Turing machines and related notions (03D10)

Related Items (2)

Algorithmically complex residually finite groups ⋮ Unnamed Item

Cites Work

• The isomorphism problem for profinite completions of finitely presented, residually finite groups.
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• The triviality problem for profinite completions
• Unsolvability of the universal theory of finite groups
• The decision problem for exponential diophantine equations
• Algorithmic problems for finite groups and finite \(0\)-simple semigroups
• Algorithmic problems for amalgams of finite semigroups
• Algorithmically complex residually finite groups
• Algorithmic problems in varieties of semigroups
• Quantifying residual finiteness.
• Automata Studies. (AM-34)
• The Potential -Relation and Amalgamation Bases for Finite Semigroups
• Finite and infinite cyclic extensions of free groups
• Word Problems Solvable in Logspace
• Potential Divisibility in Finite Semigroups is Undecidable
• ALGORITHMIC PROBLEMS IN VARIETIES
• Combinatorial Algebra: Syntax and Semantics
• SOME DUALITY CONJECTURES FOR FINITE GRAPHS AND THEIR GROUP THEORETIC CONSEQUENCES
• Some Connections between Residual Finiteness, Finite Embeddability and the Word Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Minsky Machines and Algorithmic Problems