I/O in Theory of Computation

Question

I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear.

I concluded that in any arbitrary program that halts, control flow operations, calculation operations ( 2+3 , "1 && 0", etc ) and memory assignment ( x:= "Hello" ) can be easily represented by Models of Computation such as Turing , RAM Machines, Lambda Calculus, etc.

But I/O operations such as reading input from keyboard/mouse/etc, writing output to monitor/speaker/network_device, don't really seem to have any relation to those models of computation, that is, i can't think of a way to simulate/emulate them there ( the only I/O operation that those models of computation could simulate is writing and reading from memory ) . This reflects the fact that the programming languages were meant to access not only the CPU and the memory but the entire desktop PC ( including its additional I/O devices ).

At the same time, i've some people suggest that those I/O operations correspond to computations, in the Theory of Computation sense, and i'm thinking this is a problem because Turing-complete models of computation were mean't to possibly express ANY computation.

So, there are two possibilities :
1 - Those I/O operations are not really computation and hence Turing-Complete models of computation are not required to express them, and also programming languages ( and our Desktops in general ) are modelling MORE than mere computation, they are modelling Computation + I/O.

2 - Those I/O operations are really "computation" and i simply don't know how to think of simulating them with Turing-Complete models of computation, that is, i can't seem a way to simulate the entire composition of a desktop PC ( CPU + memory + all external devices ) in those models of computation.

The first option seems more plausible to me, but i don't know.

What do you guys think about the relation between those I/O Operations and Computation ?

Answer 1

For Turing machines I/O corresponds to using the tapes:

• a disk is a tape which has been rolled up
• keyboard is the input tape
• display is the output tape

A more interesting question is how to model interaction between machines using communications channels (that's a form of I/O), especially asynchronous communication. You can look up communicating sequential processes and $\pi$-calculus to learn about computational models that account for communication (and these are not the only ones).

The $\lambda$-calculus is a bit different because it does not have a direct notion of I/O. However, in any programming language we may simulate an input or an output stream by passing around extra lists of chacarters (or bits) which represent input and output streams. Here is an example in Haskell (but using only purely functional part if Haskell without any real I/O):

    -- Simulated IO in a purely functional way in Haskell

    -- A dataype of programs which perform simulated IO and return
    -- results of type a
    data SimulatedIO a =
        Result a
      | Output String (SimulatedIO a)
      | Input (String -> SimulatedIO a)

    -- Run a simulated IO calculation on the given input stream.
    -- Return the result, the remaining (unused) input, and output.
    run :: [String] -> SimulatedIO a -> (a, [String], [String])
    run input (Result a) = (a, input, [])
    run input (Output s c) =
      let (x, input', output) = run input c
      in (x, input', s : output)
    run (s:input') (Input c) = run input' (c s)

    -- Example
    greeter :: SimulatedIO Int
    greeter =
      Output "What is your name?" -- ask the user for his name
             (Input (\name -> -- read the name
                Output ("Hello " ++ name) -- greet the user
                       (Result (length name)))) -- return the length of user's name

    -- Execute the example with simulated input ["John", "Banana", "Orange"]
    example = run ["John", "Banana", "Orange"] greeter

    -- the result is
    --
    --    (4, ["Banana","Orange"], ["What is your name?","Hello John"])
    --
    -- 4 because "John" has four characters
    -- ["Banana","Orange"] is the unused input
    -- ["What is your name?","Hello John"] is the output