Channel system (computer science): Difference between revisions

Revision as of 17:45, 15 October 2019

Revision as of 17:48, 15 October 2019

Line 39:

Most problem related to perfect channel system are undecidable{{r|decidable|p=92}}.<ref name="easier">{{cite journal |last1=Cécé |first1=Gérard|last2=Finkel|first2=Alain |title=Unreliable Channels Are Easier to Verify Than Perfect Channels|journal =Information and Computation |date=10 January 1996 |volume=124 |issue=1 |pages=20–31 |doi=10.1006/inco.1996.0003}}</ref>{{rp|22}} This is due to the fact that such a machine may simulates the run of a [[Turing machine]]. This simulation is now sketched.

Given a [[Turing machine]] <math>M</math>, there exists a perfect channel system <math>S</math> such that any run of <math>M</math> of length <math>n</math> can be simulated by a run of <math>S</math> of length <math>O(n^2)</math>. Intuitively, this simulation consists simply in having the entire tape of the simulated Turing machine in a channel. The content channel is then entirely read, and aimmediately steprewritten isin simulatedthe whilechannel, itwith one exception, the part of the content representing the head of the Turing machine is readchanged, to simulate a step of the Turing machine computation.

== Variants ==