Die Termersetzungssysteme (TES) sind ein formales Berechnungsmodell in der Theoretischen Informatik. Sie bilden insbesondere die Grundlage der Logik - und funktionalen Programmierung. Ferner spielen sie eine wichtige Rolle beim Wortproblem und bei der Terminierungsanalyse.
Termersetzungssysteme sind Mengen von so genannten Termersetzungsregeln. Diese Mengen kann man sich wie Gleichungssysteme zwischen Termen vorstellen, bei dem die Gleichungen nur von links nach rechts angewendet werden dürfen.
Die oben stehenden Regeln bilden ein Termersetzungssystem, welches als die Addition zweier natürlicher Zahlen verstanden werden kann. Dies erfordert dass man die Zahl 0 mit dem Term 0, die Zahl 1 mit dem Term succ(0), die Zahl 2 mit dem Term succ(succ(0)) usw. repräsentiert. Die Regeln besagen, dass beispielsweise jedes Vorkommen von
plus
(
0
,
y
)
{\displaystyle \operatorname {plus} (0,y)}
in einem
Term durch
y
{\displaystyle y}
ersetzt werden darf. Dabei kann
y
{\displaystyle y}
selbst ein beliebiger Term sein, muss also insbesondere auch keine natürliche Zahl darstellen.
Copyright 2024 puzzlefactory.com Alle Rechte vorbehalten.
