Recursive Unsolvability of a Problem of Thue

Post, E. L. (1947). Recursive Unsolvability of a Problem of Thue. 12(1), 1-11.

Type

Journal article

Intellectual base

Primary research

Year

1947

Link

https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/recursive-unsolvability-of-a-problem-of-thue/98F1CFB0D1BDC1F354A017329248198F

Cited from

mathematics

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Primes

• Monoid
  • Decidability does not transfer: the word problem for finitely presented monoids is undecidable, so knowing that a structure is a monoid does not mean two expressions in it can be compared.

    This sourceProves the word problem for a finitely presented semigroup, given as a Thue system on words over a finite alphabet, recursively unsolvable; the finitely presented monoid case is the same result on the free monoid with the empty word admitted.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:00c3b93f7ce1 · see in the full table