5
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ A simple model of IO is that the user input is the input of the computation and the output the user sees is the computation output. Or are you talking about modeling interactive IO? E.g. the program writes "Input your age:", the user writes their age, and the program responds to that. (The Wikipedia article about that seems to be … lacking.) $\endgroup$ – svick Feb 8 '15 at 18:00
  • $\begingroup$ So i think you are more inclined to the first possibility. Right ? $\endgroup$ – nerdy Feb 8 '15 at 18:22
7
$\begingroup$

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
$\endgroup$
  • $\begingroup$ There's supposed to be a hyperlink to $\pi$-calculus, but it's not visible, maybe because the URL contains a non-ASCII character? This is a bug then. $\endgroup$ – Andrej Bauer Feb 8 '15 at 19:37
  • $\begingroup$ So, we could roughly consider that all kinds of input or output devices are regions of a readable tape ( input tape ) and a writable tape ( output tape ), respectively, that the Turing Machine interacts with. Commands like "printf" and "scanf" in programming languages could be modeled as the state-transition-function of the Turing Machine writing and reading those respective tapes. Is that reasoning somewhat correct ? $\endgroup$ – nerdy Feb 8 '15 at 21:25
  • $\begingroup$ That's exactly correct. $\endgroup$ – Andrej Bauer Feb 8 '15 at 22:30
  • $\begingroup$ Could you please clarify the following (sorry if this is explained in your answer but I did not get it): How does one model a Turing machine that waits for input? Would the tape store a special symbol for "no input yet, please wait" and an external daemon would "change" that symbol to a valid input? AFAIU, the Turing machine model does not consider the tape being changed by an outside process. $\endgroup$ – user1202136 Apr 19 '17 at 15:44
  • $\begingroup$ The common way to model interaction, which is what waiting for input is, is to use a formalism which explicitly accounts for it. Have a look at the links in my answer. Another thing to look up is Petri nets, these model the idea that events get "triggered". In general I would advise against obsession with Turing machines. They are not holy cows, they're just the standard cows. $\endgroup$ – Andrej Bauer Apr 19 '17 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.