Sunday, February 10, 2013

What is computation?

The Interactive Nature of Computing: Refuting the Strong Church-Turing Thesis

'' The classical view of computing positions computation as a closed-box transformation of inputs (rational numbers or finite strings) to outputs. According to the interactive view of computing, computation is an ongoing interactive process rather than a function-based transformation of an input to an output. ... The paradigm shift to interaction provides an alternative understanding of the nature of computing that better reflects the services provided by today’s computing technology.'' [source]

Post-Turing machine
'' A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation ...  '' [source]

I actually remember studying a minimalistic (imperative) programming langauge that was based on few commands. I cannot remember where it came from or what was its name :(
It worked like this:
- you have as many variables as you like, V1 to Vn, and the only basic datatype is integers.
- the math operators are:
   - Vk += 1           which means: variable Vk is self incremented of 1
   - Vk -'= 1           where the -' ("minus dot") decrements Vk of 1, but if Vk is 0 the result will also be 0
   - Vk = 0             the only basic assignment
  of course to initialize V3 (for example) to 4, we can simply write:
         V3 = 0
         V3 += 1
         V3 += 1
         V3 += 1
   so we can create a short-hand notation: V3 = 4 without altering the original language
- a program is a sequence of instructions (each with an index)
- selection operator is: if Vk is 0 goto X
there is also a halt statement
- no ways to input or output.

For example, you cannot directly write Vi = Vk as an instruction, but we can make it as a small program.
The code for V2 = V1 is:

 1 V1 = 3
 2 V2 = 0
 3 if V1 is 0 goto 7
 4 V1 -'= 1
 5 V2 += 1
 6 if V3 is 0 goto 3
 7 halt

The goto X instruction does not exist, but it can be defined as:
   N        Vk = 0
   N+1   if Vk is 0 goto X
where Vk is a variable that is not used in the rest of the program.

Unfortunately the effect of the assignment V2=V1 here destroys the value that was originally in V1 :(
To fix that we could:

 1 V1 = 3
 2 V2 = 0
 3 V3 = 0
 4 if V1 is 0 goto 9
 5 V1 -'= 1
 6 V2 += 1
 7 V3 += 1
 8 goto 4
 9 if V3 is 0 goto 13
10 V3 -'= 1
11 V1 += 1
12 goto 9
13 halt

The above program should do:
   V2 = V1 and V3 = V1, with the side-effect that V1 = 0
but then

   V1 = V3, with the side-effect that V3 = 0
So all in all we get that:
   V2 = V1
and V1 stays the way it was! V3 is just used as a temporary value.

(Does anybody know what is the name of this language?)

No comments:

Post a Comment