7
$\begingroup$

In the fair cake-cutting, two different computational models are used:

  • A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies;
  • A continuous model, in which one or more "knives" move continuously over the cake under certain restrictions, until a player shouts "stop".

The continuous model is strictly stronger: there are problems that can be solved easily in the continuous model, but cannot be solved in finite time in the discrete model, e.g, envy-free cake-cutting with connected pieces.

So I wonder what other problems, besides cake-cutting, can benefit from a "moving knife" or a similar continuous model?

For example, is there a continuous variant of a Turing machine, that can easily solve problems that are unsolvable for a discrete Turing machine?

| cite | improve this question | |
$\endgroup$
  • 4
    $\begingroup$ Well, this is a toplogical result, which belongs to a large family of pretty nice results (it is essentially a fixed point theorem). Among them is Kakatoni fixed point theorem, which implies the Nash equilibrium result. Matousek book on topology is a good point to start reading on this stuff (warning - its mathematically not easy stuff). springer.com/us/book/9783540003625 $\endgroup$ – Sariel Har-Peled Apr 2 '15 at 13:45

Your Answer

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

Browse other questions tagged or ask your own question.