[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: Material from UIML DISL Discussion
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>
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]