.. -*- coding: utf-8 -*-












.. role:: sref(numref)
.. role:: xref(numref)
.. Copyright (C) 2019, Wolfgang Scherer, <Wolfgang.Scherer at gmx.de>
..
.. This file is part of Development.
..
.. Permission is granted to copy, distribute and/or modify this document
.. under the terms of the GNU Free Documentation License, Version 1.3
.. or any later version published by the Free Software Foundation;
.. with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
.. A copy of the license is included in the section entitled "GNU
.. Free Documentation License".

.. inline comments (with du_comment_role)
.. role:: rem(comment)
.. role:: html(raw)
   :format: html
.. role:: shx(code)
   :language: sh

.. rst-class:: narrow xmedium xlarge xhuge xultra

##################################################
:rem:`|||:sec:|||`\ MOV is Turing-complete
##################################################
.. >>CODD See `the components of a doctoral dissertation and their order <http://site.uit.no/english/writing-style/bookstructure/>`_
.. >>CODD Dedication
.. >>CODD Epigraph
.. >>CODD Abstract

.. compound::

   No, **mov** is **not** Turing-complete. There must be

   - either an additional **jmp** instruction
   - or separate data and program memory, where program memory is

     - finite with wrap-around,
     - or infinite.

   See also rebuttal on reddit `mov is Turing-complete by Stephen Dolan: ReverseEngineering`_.

   .. \|:here:|

.. _`mov is Turing-complete by Stephen Dolan: ReverseEngineering`: https://www.reddit.com/r/ReverseEngineering/comments/1lfm21/mov_is_turingcomplete_by_stephen_dolan_pdf/

.. >>CODD Introduction
.. >>CODD Chapter

1. Eine Turing-Maschine mit ausschließlich **mov**-Instruktion ist
   **nicht realisierbar**.

   Das großspurig angekündigte `mov is Turing-complete - Cambridge
   Computer Laboratory
   <https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwi6p-jv-_zgAhUB3qQKHesoA9EQFjAAegQIAhAC&url=https%3A%2F%2Fwww.cl.cam.ac.uk%2F~sd601%2Fpapers%2Fmov.pdf&usg=AOvVaw1MT9h-nrQNHDyCrFggsGc0>`_
   (Dokument ist nicht mehr verfügbar. `Lokaler Link
   <_static/mov.pdf>`_) bringt nicht neues und auf Seite 4 wird die
   Katze dann aus dem Sack gelassen. Es braucht einen **jmp** Befehl:

        ... in a suitable state to run the program again, so we use
        our single unconditional jump to loop back to the start::

            jmp start

        This simulates an arbitrary Turing machine, using only mov
        (**and a single jmp** to loop the program).

2. Es gibt auch keinen C-Compiler, der nur mit **mov** geschrieben ist
   (obwohl man das natürlich realisieren kann, wenn man sehr viel
   Speicher übrig hat).

   Es gibt eine LCC-Erweiterung `M/o/Vfuscator2
   <https://github.com/xoreaxeaxeax/movfuscator>`_ die ein C-Programm
   in **mov**-Instruktionen übersetzt. Dieses Programm selbst ist aber
   in C geschrieben.

   Und der Autor redet sich ebenfalls die Welt schön. Im Abschnitt
   `Notes`:

       While Dolan's paper required a jmp instruction, the
       M/o/Vfuscator does not - it uses a **faulting mov
       instruction** to achieve the infinite execution loop.

       If you're worried that this is still "jumping", the same
       effect could be achieved through

       a) **pages aliased to the same address**,
       b) **wrapping execution around the upper range of memory**,
       c) **ring 0 exception handling**,
       d) or simply **repeating the mov loop indefinitely**.

       \...

   Die Punkte a) - c) sind alles mehr oder weniger verdeckte Sprünge!

   Wobei Punkt a) wenigstens noch als Endlosband denkbar ist. Das
   sollte man aber auch klar und deutlich spezifizieren. Auf jeden
   Fall ist es dann Essig mit gemeinsamem Programm- und
   Datenspeicher. Die müssen dann auf jeden Fall getrennt sein. Und
   damit braucht es eine nichtexistente (aber realisierbare) CPU.

   Punkt d) ist illusorischer Quatsch. In diesem Fall haben wir eine
   CPU mit getrenntem Programmspeicher und Datenspeicher, wobei der
   Programmspeicher unendlich groß ist. Also nichts realisierbares,
   weil es keine finiten Register geben kann, die eine unendlich große
   Adresse speichern könnten. Mit einem :math:`\aleph_0` basierten
   Zahlensystem bräuchte so ein Register allerdings nur ein
   A-Bit. Dagegen wären wohl Q-Bits bloß ein schwacher Abklatsch.

3. Wenn man also sowieso einen **jmp** braucht, dann kann man auch
   gleich einen bedingten Sprung nehmen und hat damit im Wesentlichen
   genau das existierende und realisierte Konzept einer
   von-Neumann-Maschine. Die zusätzlichen arithmetischen, logischen
   und Schiebeoperationen sind dann halt einfach sinnvoller Luxus.

Das ganze ist also ein reichlich sinnloses Unterfangen, das nicht mal
intellektuell anspruchsvoll ist, weil es mit Desinformation
arbeitet. Irgenwelche Schlußfolgerungen daraus zu ziehen ist
hanebüchen ;-) `Brainfuck <https://de.wikipedia.org/wiki/Brainfuck>`_
und `Malbolge <https://de.wikipedia.org/wiki/Malbolge>`_ sind
wenigstens amüsant und nicht so prätentiös.

.. >>CODD Conclusion
.. >>CODD Appendix A

.. \|:here:|

.. >>CODD Notes
.. ==================================================
.. :rem:`|||:sec:|||`\ Footnotes
.. ==================================================

:html:`<hr>`

.. \[#]

.. >>CODD Reference List/Bibliography
.. ==================================================
.. :rem:`|||:sec:|||`\ References
.. ==================================================

.. include:: doc_defs.inc
.. include:: doc_defs_combined.inc
..
  .. \||<-snap->|| doc_standalone
  .. include:: doc/doc_defs_secret.inc
  .. \||<-snap->|| doc_standalone
  .. \||<-snap->|| not_doc_standalone
  .. include:: doc_defs_secret.inc
  .. \||<-snap->|| not_doc_standalone

.. _`Wolfgang Scherer`: wolfgang.scherer@gmx.de