A naive questioin about UML and Turing completeness

Question

Hello! It'a a well-known fact that UML does not Turing complete (in contrast to usual programming languages). But it seems to me UML is even more flexible than traditional languages. I can't imagine a problem you can describe by means of such language as C++ (f.e) but at the same time can't describe by means of UML. Quite the contrary it's much more easier for me to fancy a construction existing in UML but unreliazable in C++ (Java, Delphi, VB and so on...) Could you help me to understand this moment? I really can't catch it.

Answer 1

Interesting question. A couple of points come to mind, although there's probably a whole more to it. Apologies it's quite long.

What can you describe with e.g. C++ that you can't describe with UML?

First, you have to define what you mean by "UML". Generally, people tend to mean the 'core' elements - those on Class Diagrams, State Diagrams, Activity Diagrams etc. - plus OCL (the constraint language).

Given those elements you can't specify imperative algorithms. Specifically, anything that requires assignment. You can however get very close: the steps and decision logic can be expressed using e.g. Activity Diagrams, and the function of each step defined as pre- and post-conditions in OCL. However, you never quite get to fully specifying the behaviour. Take an example of an atomic step whose purpose is to increment the value of an integer. The input is an integer - say X. The output is described by the post-condition X == X@pre+1. However, there's nothing in UML to actually implement the step.

Now it's entirely conceivable to extend usage of UML to address above. The UML Action Semantics were developed precisely to enable specification of actions. Doing so makes the language computationally complete. The problems are merely practical:

1. There's no universally agreed and adopted syntax for the semantics;
2. There are very few implementations

What can you describe with UML that can't be implemented in e.g. C++?

In essence nothing. However there are two practical limitations:

1. UML "specifications" are usually imprecise, ambiguous and/or incomplete. Activity Diagrams, for example, often leave paths dangling. Could it be represented directly in C++? Yes. Would it compile? No.
2. Some of the mappings for UML constructs to imperative, stack based languages are non-trivial. State Models are an example: while there are well-known patterns, the mapping is quite complex. This is especially true for hierarchical and/or concurrent behaviour. In an activity Diagram, it's easy to express that two activities happen in parallel and then synchronise before moving to the next step. That can of course be done in C++ but requires the use of e.g. threading libraries.

It can however be done. In fact, it's what the Executable UML tools do: Model Compilers take an executable UML model and translate it into 100% functioning imperative code.

hth.

Answer 2

I´d say that UML IS a turing complete language since the addition of the Action Semantics package (this happened in UML 1.5 version).

Now UML includes an imperative action language (not to be confused with OCL) that allows a precise definition of the behaviour of class methods. This imperative action language includes the typical set of assignments, if conditions, iterators,... you´d expect from any programming language.

This action language is one of the popular components of Executable UML approaches but it´s now part of the UML standard itself

Answer 3

As the name implies UML is a modelling language. It can sometimes be applied as a methodology for designing software.

Once upon a time they were dreaming up ways of automatic code generation, they were called CASE tools. They failed to get the code generators to work effectively, although they did remove a lot of boiler plate code from the language. This augmentation became the key to UML as it provided a way to augment the experience of designing and programming software.

I don't know if UML is "Turing Complete", I hope it is, wouldn't it be great to come up with solutions by describing the problem to the computer in pictorial format and letting the computer do all that hard nasty programming for you.

UML is the meta language to the doing in the code. It describes artefacts, how they relate/interact and what they do.

UML is being added to, new design artefacts are being added year by year, and if it is not already Turing Complete I don't see why it couldn't be.

However I think somewhere along the line I read something about languages being "Turing Equivalent" if they could both express and solve the same solution.

Since UML is the design language and code is the implementation language based on the UML design I would say that UML and code (c#, java, etc) are Turing Equivalent. If they are agreed to be Turing Equivalent then UML must be Turing Complete.