**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 ﬁnite 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 reﬂects 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?)*

## Sunday, February 10, 2013

### What is computation?

By at 15:27

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment