Material from UIML DISL Discussion

["Robbie Schaefer" <robbie@c-lab.de>]

Hi all,

as discussed yesterday, I attach the skeched proof of turing
completeness of DISL. Please take a careful look at it, as I am
not a formal languages expert and might have missed something.

Furthermore, I give you some URLs which fit to the questions 
submitted by Jean, regarding Muldimodality:

http://iihm.imag.fr/bouchet/ICARE/
http://www.limsi.fr/Individu/martin/publications/download/16-Martin.pdf
  

Best Regards,
Robbie
--
   _/ Dipl. Inf. Robbie Schaefer _/ Phone: +49 5251 60-6107  _/
  _/ Visual Interactive Systems _/ Fax: +49 5251 60-6065    _/
 _/ C-LAB Fuerstenallee 11     _/                          _/
_/ D-33102 Paderborn          _/ URL: http://www.c-lab.de _/
There are basically three approaches to proof that a language is Turing-complete. These are:

1.) Show there is some mapping from each possible Turing machine to a program in the language.
2.) Show that there is a program in the language that emulates a Universal Turing Machine.
3.) Show that the language is equivalent with (or a superset of) a language that is known to be Turing-complete.

Proof of Turing completeness as described in point 1.):


Mapping of the input tape:

The input tape of a turing machine is an array of spaces. Each space can have the contents {0,1,B (blank)}. We map this
array on a DISL-Structure, where we consider each space as a widget. Each widget will be ordered on the XML 
follower-axis. Example:

Tape: B010B

DISL-Structure:

<structure>
	<widget id="space0" generic-widget="variablefield"/>
	<widget id="space1" generic-widget="variablefield"/>
	<widget id="space2" generic-widget="variablefield"/>
	<widget id="space3" generic-widget="variablefield"/>
	<widget id="space4" generic-widget="variablefield"/>
</structure>

<style>
	<part generic-widget="space0">
		<property id="value">B</property>
	</part>
	<part generic-widget="space1">
		<property id="value">0</property>
	</part>
	<part generic-widget="space2">
		<property id="value">1</property>
	</part>
	<part generic-widget="space3">
		<property id="value">0</property>
	</part>
	<part generic-widget="space4">
		<property id="value">B</property>
	</part>
</style>



Mapping of the transition rules:

5-tuple formulation of a turing machine transition:

<Stateold, Symbol, Statenew, Symbolnew, Move>

Move is of {left,right}
Symbol is of {0,1,B}
Symbolnew is of {0,1,B}

Example turing transition:
<state0,1,state0,0,left>

Example in DISL:

<behavior>
	<variable id="currentPos" type="widget" widgetpointer="none">space0</variable>
	<variable id="currentState" type="String">state0</variable>

	<rule id="spacehascontent1">
		<condition>
			<equal>
				<property-content widget-id="currentPos" property-id="value"/>
				<constant>1</constant>
			</equal>
		</condition>
	</rule>


	<rule id="spacehascontent0">
		<condition>
			<equal>
				<property-content widget-id="currentPos" property-id="value"/>
				<constant>0</constant>
			</equal>
		</condition>
	</rule>


	<rule id="spacehascontentB">
		<condition>
			<equal>
				<property-content widget-id="currentPos" property-id="value"/>
				<constant>B</constant>
			</equal>
		</condition>
	</rule>

	<rule id="isinstate0">
		<condition>
			<equal>
				<variable-content variable-id="currentState"/>
				<constant>state0</constant>
			</equal>
		</condition>
	</rule>

	<transition>
		<if-true rule-id="isinstate0" expression="and">
			<if-true rule-id="spacehascontent1"/>
		</if-true>
		<action>
			<!-- Writing a 0 in space --!>
			<statement assignment="set">
				<property-content widget-id="currentPos" property-id="value"/>
				<constant>0</constant>
			</statement>
			<!-- Going left --!>
			<statement>
				<variable-content variable-id="currentPos"/>
				<widget-pointer widgetpointer="last"/>
			</statement>
		</action>
	</transitions>
</behavior>