Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/576222405665882112
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
nerdy
  • 371
  • 1
  • 7

I/O in Theory of Computation

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 ?