| Word Problem (mathematics) |
Article Index for Word Problem |
Website Links For Word |
Information AboutWord Problem (mathematics) |
|
In Mathematics and Computer Science , a word problem for a set S with respect to a system of finite encodings of its elements, is the algorithmic problem of deciding whether two given representatives represent the same element of the set. BACKGROUND AND MOTIVATION Many occasions arise in mathematics where one wishes to use finitely much information to describe an element of (typically infinite) set. This issue is particularly apparent in computational mathematics. Traditional models of computation (such as the Turing Machine ) have storage capacity which is unbounded, so it is in principle possible to perform computations with the elements of infinite sets. On the other hand, since the amount of storage space in use at any one time is finite, we need each element to have a finite representative. For various reasons, it is not always possible or desirable to use a system of ''unique'' encodings, that is, one in which every element has a single encoding. When using an encoding system without uniqueness, the question naturally arises of whether there is an algorithm which, given as input two encodings, decides whether they represent the same element. Such an algorithm is called a ''solution to the word problem'' for the encoding system. THE WORD PROBLEM IN UNIVERSAL ALGEBRA In Algebra , one often studies infinite algebras which are generated (under the finitary operations of the algebra) by finitely many elements. In this case, the elements of the algebra have a natural system of finite encoding as expressions in terms of the generators and operations. The word problem here is thus to determine, given two such expressions, whether they represent the same element of the algebra. The word problem is of particular importance in the study of Semigroup s and Groups (see Word Problem For Groups ). |
|
|