Водители одновременно выбирают двигаться прямо или перейти в другую полосу. Если кто-то принял решение свернуть, он завершает манёвр, даже если другой водитель поехал туда же.

Вариант "остановиться" не принимается!
Можно одновременно подавать любые сигналы, при условии что машины неразличимы (не принимается вариант "машина с большим номером" сворачивает).

Есть ли детерминированный алгоритм, гарантирующий отсутствие столкновения?

Никаких ПДД в условии задачи не предполагается.
Водители ничего друг о друге не знают.
Они могут быть как из страны с левосторонним движением, так и из страны с правосторонним движением.

Договорённостей между водителями перед встречей быть не должно. Любые указания друг другу только в процессе движения при условии одновременного приёма и исполнения.

White OwlqyyedДоговорённостей между водителями перед встречей быть не должно. Любые указания друг другу только в процессе движения при условии одновременного приёма и исполнения.Ну в общем-то все примитивно, каждый из водителей действует по схеме:
1. Я еду по полосе и не дергаюсь.
2. Я вижу что по моей полосе мне навстречу едет кто-то.
3. Если я вижу что встречная машина мигает поворотником - я не дергаюсь
4. Если встречная машина не мигает - тогда начинаю мигать я и продолжаю смотреть на встречную машину.
5. Если я мигаю а встречная нет я перехожу на другую полосу.
6. Если я мигаю и мигает встречная я выключаю мигалку и перехожу в состояние 3.
7. goto 1

Этот алгоритм может упасть только в одном случае: абсолютная синхронность состояний 4-6. Но это можно решить введя случайную задержку на 6-ом состоянии. Через сколько секунд выключать свою мигалку чтобы рассинхронизороваться.
Практически все как в жизни :)

Одновременность действий является очень важным условием задачи.
Вот вы оба включили поворотник с интервалом 0.01 с (за такое время никак не среагируешь). Тогда вы или оба повернёте (переход на п. 2), или оба будете ждать пока другой повернёт, пока не столкнётесь.
С помощью случайных задержек можно построить алгоритм, дающий малую,но ненулевую вероятность столкновения.
А надо построить алгоритм с нулевой вероятностью столкновения, или доказать, что его не существует.

Да хрен с этими машинами ) Здесь никаких ПДД уж точно )

Летите вы в космосе на космическом корабле, а прямо навстречу корабль инопланетян. Как будете расходиться?

White OwlqyyedДа хрен с этими машинами ) Здесь никаких ПДД уж точно )

Летите вы в космосе на космическом корабле, а прямо навстречу корабль инопланетян. Как будете расходиться?Инопланетяне? То есть не имеющие со мной ничего общего и не понимающие моих сигналов так же как я не понимаю их сигналов?
Тогда просто дам импульс сдвигающий мой корабль в случайном направлении и буду молиться что они не дадут импульс в том-же направлении с той-же скоростью. А если увижу что таки-да, они сместились с прежней прямой полета и опасность столкновения сохраняется - дам второй, третий импульс...

Ну а если у нас с ними уже есть что-то общее - хотя бы те-же поворотники, то задача сводится к предыдущей и решается так как уже показано.

Будем считать, что поворотники у вас обоих есть, и инопланетяне понимают что они обозначают.
Расстояние когда вы заметили друг друга достаточно чтобы дать понять друг другу что когда вы мигаете поворотником, вы поворачиваете в ту же сторону.
Решение с использованием поворотников - в студию.

Вероятностное решение не принимается. Алгоритм должен гарантировать отсутствие столкновения.

Программист 1сОба пытаются захватить некие данные (одна чашка кофе на двоих) кто ее первый заблокировал тот и прав(право едет)
Схватили оба сразу. Что им делать?

AkinaqyyedЕсть ли детерминированный алгоритм, гарантирующий отсутствие столкновения?
Машина, едущая по левой для себя полосе, немедленно перестраивается вправо.
Едут навстречу русский и англичанин. Русский по своей правой, а англичанин по своей левой. Кто будет сворачивать?