В идеале смысл многопоточности состоит в общении потоков между друг другом. Т.е. когда один поток говорит другому "о, коллега, у меня тут запрос пришёл и кое-что обновилось - обнови ка и у себя это". mayevski выше сказал - мол, если есть куча процессов - нафиг городить многопоточность.. а вот представьте себе 128 ядер. И у них есть общая настроечка такая - скажем счётчик посещений. Вы только представьте сколько можно сэкономить буквально на этой мелкой штуке если использовать распределённую память. Только при этом особый выигрыш будет при традиционной shmem и pthreads и, как следствие, Си. В других же случаях, тот же APC у пхп при обслуживании 128 потоков грозит быть затычкой для них всех (т.к. лочить будет).
Чтобы сделать общий счётчик на общей памяти, нужно будет устраивать синхронизацию. А теперь представьте, что у вас 128 нитей выполнят lock и будут ждать друг дружку довольно долго. И простаивать. Зачем тогда 128 ядер и нитей? Да и вообще, 128 ядер с общей памятью - это несколько безумно. Узкое место современных систем - это совсем не скорость работы процессоров, а скорость работы памяти. Шины кое как с двумя ядрами справляются, а тут их в 64 раза больше. Зачем вся эта лишняя электроника, если она будет сама себя тормозить при каждом обращении в память?
Вообще говоря, SUN проводила исследования того, насколько масштабируются аппаратура с общей памятью и приложения с нитями, и оказалось, что даже при 32 процессорах расходы на различную синхронизацию составляют 20% процессорного времени. Не так уж и мало.
Поэтому, если в системе, вдруг, появляется общий счётчик у 128 задач, то это какая-то явная ошибка в проектировании.
При условии правильной реализации, таски можно запускать десятки-сотни тысяч раз в секунду.
Т.о. можно параллелить каждый чих.
Сейчас затраты на создание трэда в сотни раз больше чем нужно.
Хотя подобный планировщик можно построить и на существующих системах,
но он утонет в синхронизации.
Если запустить две задачи, то на одном процессоре каждая из них будет работать в два раза медленней, плюс затраты на переключение контекстов, которые растут линейно от количества задач. Осмысленно ли в этих условиях параллелить каждый чих?
Кроме того, существует техника создания пуллов нитей или процессов, которые способны очень быстро начинать исполнение указанной работы. При этом используется такая логика: выделили вычислительные ресурсы, затем начали их использовать, без повторных выделений и уничтожений. Скорость создания перестаёт быть критичной.
А это хорошо, потому что создание новой задачи - это не такая уже простая операция - как эффективно её не программируй, но нужно выделять память под контекст и под стек ядра, инициализировать некоторые служебные структуры, ставить задачу в очередь исполнения и так далее. Можно сделать очень эффективно, гораздо эффективнее, чем в Linux или Windows, но это будет всё-равно медленней, чем заказ задаче из пула произвести вычисление.
Про регистры не понял. Какое отношение они имеют к многозадачности?
Наоборот, с ними проблем больше - надо сохранять/восстанавливать.
Как раз это и гарантирует то, что можно сохранить состояние вычисления и перейти к другому вычислению. То есть, организовать многозадачность.
Про первое я и говорю, со вторым не согласен. Сколько вы на запорожце не пишите F1 pro street racing он от этого быстрее не побежит.
Аналогия неверная. Скорее так: и Porsche, и Запорожец состоят из примитивных деталей, работающих по одинаковым принципам. Чем шестерёнки в Porsche концептуально лучше шестерёнок в Запорожце? Другое дело, как эти примитивые собрать и какой к ним приложить интерфейс.
Существуют различные современные ОС. И в них процессами называется разное.
И вопрос: а чем поддержка виртуальной памяти, например, не является аппаратной поддержкой процессов? Собственно, для процесса больше ничего и не нужно от аппаратуры. Остальное абстрагирование - это уже задача операционной системы. И прикладник видит именно то, что даёт ему ОС, а не то, что даёт ему железо.
Кроме того, Вы ошибаетесь насчёт понятия нити и задачи. Потому что для вычисления одного кода недостаточно, нужны данные, нужен процессор, нужна память, etc. И для прикладника (правильного прикладника) нить - это более или менее независимая задача от других задач (о параллельности речь может и не идти совсем). При этом, независимость может быть очень разная. Апогей независимости - это процесс, поэтому он никак не может стать нитью, или поднитью, или подподнитью. Наоборот, развязка нитей приблежает их к процессам и даёт возможность, например, приложению работать на нескольких компьютерах. Разделение адресных пространств - это благо.
И програмное распараллеливание никуда не уйдёт. Возможно, оно будет производиться автоматически, но уж точно программным способом. Все современные архитектуры: Cell, VLIW, EDGE, multicell - это упрощение железа за счёт добавления мозгов компилятору и операционной системе.
Неа. Это только кажется, что в потоках это проще. Общая память с синхронизацией через разнообразные lock'и и события, обычно выходит логически более сложной, чем простой pipe между двумя процессами. К этому можно добавить необходимость считать ссылки, следить за буфферами памяти, развешивая на них конечные автоматы, и так далее.
Общемировой опыт, изложенный, например, в taoup, говорит о том, что это как раз правильные нити превращаются в нечто подобное процессам: взаимодействие через очереди сообщений (аналог pipe'ов или socket'ов) и явная привязка нитей к обрабатываемым общим данным (аналог mmap). Мой собственный опыт разработки чего-то более или менее надёжного и эффективного это подтверждает.
И в чём же его правильность? Какая по большому счёту разница: task/не task? Если у Вас вытесняющая многозадачность (multitasking), то состояние и планирование так или иначе нужны. Если многозадачность, например, кооперативная, или пакетная, или ещё какая-нибудь древняя, то система будет убиваться хакерами на счёт 'раз'.
От синхронизации тоже никуда не сбежать. Если файловая система одна, то 10 задач (tasks) работать с ней без синхронизации в каком-либо виде не смогут. Хоть синхронно, хоть (и даже тем более) асинхронно. Поддержка этого всего может быть аппаратной или не аппаратной, но проблемы с потерями производительности на ожидания и со сложностью протоколов взаимодействия она не решит.
Менять надо сам способ описания параллельных программ, а не механизмы поддерживающие работу многозадачных систем. Кстати, в любом современном процессоре есть куча примитивов для поддержки именно многозадачности: начиная с прерываний, режима ядра, специальных инструкций, вроде cmpxchgl, регистров (регистры на самом деле - это именно средства поддержки многозадачности. Существуют процессоры без регистров и на них с многозадачностью довольно туго), заканчивая алгоритмами синхронизации кэшей. Разве этого мало?
Да и P.S. очередной: многие современные компиляторы, даже gcc с недавних пор поддерживают автоматическое распараллеливание программ. Копать в сторону OpenMP.
Почему-то все забывают про процессы. Это гораздо более удобный метод организации многозадачной обработки, чем нити. И гораздо более эффективный в реализации в ядре операционной системы. У процессов много достоинств, а единственный недостаток - это сложность переключения контекста виртуальной памяти. Но в нормальных процессорах поддержка уже давным давно сделана на аппаратном уровне через идентификаторы виртуальных адресных пространств. На ненормальных, то есть, производных от x86, проблема решается через хитрые кэши первого уровня.
Вобщем, затраты на переключение контекста процесса по сравнению с контекстом нити в худшем случае составляют +200 тактов. При этом, затраты на синхронизацию при программировании с нитями и усложнение основных служб ядра операционной системы эти 200 тактов с лихвой перекрывают.
Процессы снимают проблему со стеками и со сборкой мусора, вполне естественным образом: стеки различны, а при завершении процесса все занимаемые ресурсы можно освободить.
Сложность в параллельном программировании упирается не в создание или управление задачами (нитями или процессами), а в сложность описания взаимодействия между ними. Собственно, кажется, в данный момент известно, от куда у этого усложнения по сравнению с обычным программированием ноги растут и работы по исправлению ситуации ведуться. Уточнять не буду, пока статью не опубликую, но желающие могут посмотреть в направлении Linda.
У Вас взаимодействие между этими нитями есть? Такое ощущение, что вряд ли. Вот когда появится, когда встанут проблемы синхронизации, когда планировщик начнёт у Вас бросать эти нитки по процессорам с большими кэшами, как попало, тогда и увидите все прелести многопоточного программирования.
P.S. Маленький вопрос: процессор в 3 гигагерца - это же pentium 4 не самый новый, то есть 32 битный процессор. Если Вы писали под Windows, то для приложения доступное виртуальное адресное пространство составляет 2 гигабайта. А для каждой нити отводится по умолчанию по мегабайту стека, меньшие же стеки опасны, обычно. Как вы умудрились запустить одновременно 10 тысячь нитей, работающих с сетью через динамические библиотеки, требования к объёмам стеков у которых заранее не известны?
Микроконтроллер Atmel - это, в том числе, готовый микропроцессор хорошо известной архитектуры. А люди сами проектируют и собирают, в том числе, и процессоры. В этом разница, и это удивляет. Можно такую деятельность сравнивать с программированием FPGA, но FPGA - это не хардкор с паяльником наперевес.
Хмъ. Идея становится ничем, как раз в тот момент, когда продукт реализован. Но до этого момента она может быть весьма достойным товаром. Лично у меня есть положительный опыт продажи чистой идеи. Хотите продам вам идею того, как можно продавать идеи? : )
Тык. Об этом и речь. Если мне понадобиться другое вычисление, то нужно будет поменять интерфейс, а если мы поменяем интерфейс, то не поменяется ли внутреннее представление данных? Не появиться ли необходимость всё переписать заново?
В императивном же варианте решения, у меня все данные будут торчать наружу. И я в любой момент смогу начать визуализацию, хоть в параллельном режиме, просто скопировав некоторые данные на stdout или передав их другой нити.
Это можно запроектировать и в объектной модели, но это потребует очень многих размышлений, которые вобщем-то будут не самыми очевидными. А императивное программирование нужные интерфейсы, в конце концов выявит в процессе программирования.
Вы уже такие примеры привели - системы с обратной связью. Сервер какой-нибудь, или, более формальный пример: дана случайная величина x(t) (t - дискретное время), с областью значений {3, 4, 5}, вычислить случайную величину 2x(t).
Вот. Конечно, такую задачу можно решить организовав систему обслуживания, с классической MT в центре, которая умножает конкретное число на два. Но вся система уже не будет эквивалентна МТ в строгом смысле. Хотя бы по той причине, что всевозможных случайных величин континуум, а всевозможных лент у любой МТ - счётное количество.
Ещё раз повторю свой запрос: пожалуйста, приведите алгоритм в виде посылок сообщений, учавствующим в предлагаемой модели игры объектам.
По идее, следующее должно стать очевидным. (1) такая опять же априорная модель разбиеня задачи, которая опирается на понятия, существующие в голове программиста, до анализа решения: стержни очень похожи на стек, следовательно, да будет стек в модели - не полная. Для построения эффективного генератора последовательности ходов, по идее, должен понадобиться объект 'самый мелкий кружочек', который должен будет хранить информацию о предыдущем её перемещении.
(2) Такой алгоритм тоже не сможет начать строительство программы ходов для бесконечной башенки, он будет опираться на значения, записанные в стек, а в стек не влезет бесконечная башенка. Можно, конечно, и тут ООП показывает свою приятную сторону, один из стеков сделать таким, что он никогда не пуст и выдаёт (N + 1), когда выполняется pop, а он пуст.
Но этот подход по сравнению с переписыванием программы, которое (подчеркну) достаточно просто возникает при взгляде на то, какие процессы происходят при перемещении кружочков, и требует чуть больше интеллектуальных усилий, что и рекурсивные построения, будет требовать всё более и более длинные ячейки для хранения элементов стека. То есть, понадобится реализовать ещё один объект: число с переменной длинной. Ещё немного головной боли ОО программисту, imho.
P.S. пример с крестиками и ноликами очень хорош: классическая машина Тьюринга не может сыграть в крестики и нолики, а компьютер может.
А почему по вашему мнению теорема о существовании\не существовании универсальной машины - это не свойство модели?
Понятия мощность и эквивалентность - обычные из математической логики. Хм... Ну. Так и быть, дам определения:
Мощность - это множество задач, для которых существует алгоритм в рамках этой модели. Чем больше задач во множестве, тем модель мощнее.
Для алгоритмов в разных моделях эквивалентность определяется следующим образом: пусть A и B - преобразования над входом, выполняемые двумя алгоритмами соответсвенно. Пусть алгоритмам на вход могут быть поданы данные из множеств IA и IB, а в результате алгоритмы выдают результаты в виде элементов множеств OA и OB, соответсвенно. Если существуют изморофизмы o: OB -> OA и i: IA -> IB, такие, что o(B(i(x)) = A(x), то алгоритмы A и B называются эквивалентными.
МТ с вводом/выводом - это обычная машина Тьюринга с дополнительными регистрами ввода (вывода), в которых в каждый момент времени может присутствовать один из символов алфавита ленты. А множество комманд такой машины, кроме классических, включает так же в себя комманды вида a, S1 -> get (set), S2, где put означает запись на ленту символа из регистра ввода (чтение с ленты буквы и помещение её в региср вывода).
Понятие вычислимости здесь иное. Считается, что такая машина вычисляет функцию (или уже можно говорить об операторах), если в регистр ввода подаётся последовательность букв, кодирующая input задачи, а на выходе получается последовательность, кодирующая output.
Последовательности потенциально могут быть бесконечными, и это ни сколько не противоречит теоретическим возможностям компьютера: например, очень устойчивая база данных.
Кстати : ) Вы тоже начинаете демонстрировать то, что я предписываю ОО проектированию - начали описывать всё сверху. Но тут возникают вопросы, а от куда вдруг стало известно, что nextstep и move - наилучший интерфейся для игры? От куда известно заранее, что такой интерфейс не ограничит вас в дальнейшем в выборе алгоритма решения задачи, не приведёт к лишним вспомогательным вычислениям?
Давайте разберёся с этим примером до конца. Итак, теперь у нас три стека и класс game с указанным интерфейсом, что дальше?
Ещё одно важное свойство: бесконечно много МТ, работающий параллельно так же вычислительно эквивалентны одной МТ, по той причине, что данные нужно выложить на ленты до начала вычислений. А дальше каждая начнёт мариновать данные по своему усмотрению, и они никак не смогут повлиять на ход вычислений в других машинах.
Бесконечное множество МТ с I/O, способные друг другу сообщать о результатах расчётов - не эквивалентны одной такой машине, и обладают огромной вычислительной мощностью.
Возможно, конечно, представить машину с I/O цепочкой классических машин, которые обрабатывают данные друг за дружкой, но эта цепочка должна быть (1) бесконечной, следовательно (2) эта модель не сводится к классической МТ, обладающей лишь конечным числом состояний.
Можно, но N параллельно работающих классических машин Тьюринга - это то же самое по своей мощности, что и одна классическая машина Тьюринга.
И потом. В обычном компьютере задачи могут во время вычислений обмениваться данными. В классической MT никаких обменов со внешним миром во время работы не предусматривается - это самое важное отличие от машины с вводом/выводом. Это влияет на то, что машина может делать и с какими данными оперировать, и на математические свойства модели (в очередной раз повторяюсь).
Чтобы сделать общий счётчик на общей памяти, нужно будет устраивать синхронизацию. А теперь представьте, что у вас 128 нитей выполнят lock и будут ждать друг дружку довольно долго. И простаивать. Зачем тогда 128 ядер и нитей? Да и вообще, 128 ядер с общей памятью - это несколько безумно. Узкое место современных систем - это совсем не скорость работы процессоров, а скорость работы памяти. Шины кое как с двумя ядрами справляются, а тут их в 64 раза больше. Зачем вся эта лишняя электроника, если она будет сама себя тормозить при каждом обращении в память?
Вообще говоря, SUN проводила исследования того, насколько масштабируются аппаратура с общей памятью и приложения с нитями, и оказалось, что даже при 32 процессорах расходы на различную синхронизацию составляют 20% процессорного времени. Не так уж и мало.
Поэтому, если в системе, вдруг, появляется общий счётчик у 128 задач, то это какая-то явная ошибка в проектировании.
Т.о. можно параллелить каждый чих.
Сейчас затраты на создание трэда в сотни раз больше чем нужно.
Хотя подобный планировщик можно построить и на существующих системах,
но он утонет в синхронизации.
Если запустить две задачи, то на одном процессоре каждая из них будет работать в два раза медленней, плюс затраты на переключение контекстов, которые растут линейно от количества задач. Осмысленно ли в этих условиях параллелить каждый чих?
Кроме того, существует техника создания пуллов нитей или процессов, которые способны очень быстро начинать исполнение указанной работы. При этом используется такая логика: выделили вычислительные ресурсы, затем начали их использовать, без повторных выделений и уничтожений. Скорость создания перестаёт быть критичной.
А это хорошо, потому что создание новой задачи - это не такая уже простая операция - как эффективно её не программируй, но нужно выделять память под контекст и под стек ядра, инициализировать некоторые служебные структуры, ставить задачу в очередь исполнения и так далее. Можно сделать очень эффективно, гораздо эффективнее, чем в Linux или Windows, но это будет всё-равно медленней, чем заказ задаче из пула произвести вычисление.
Про регистры не понял. Какое отношение они имеют к многозадачности?
Наоборот, с ними проблем больше - надо сохранять/восстанавливать.
Как раз это и гарантирует то, что можно сохранить состояние вычисления и перейти к другому вычислению. То есть, организовать многозадачность.
Про первое я и говорю, со вторым не согласен. Сколько вы на запорожце не пишите F1 pro street racing он от этого быстрее не побежит.
Аналогия неверная. Скорее так: и Porsche, и Запорожец состоят из примитивных деталей, работающих по одинаковым принципам. Чем шестерёнки в Porsche концептуально лучше шестерёнок в Запорожце? Другое дело, как эти примитивые собрать и какой к ним приложить интерфейс.
И вопрос: а чем поддержка виртуальной памяти, например, не является аппаратной поддержкой процессов? Собственно, для процесса больше ничего и не нужно от аппаратуры. Остальное абстрагирование - это уже задача операционной системы. И прикладник видит именно то, что даёт ему ОС, а не то, что даёт ему железо.
Кроме того, Вы ошибаетесь насчёт понятия нити и задачи. Потому что для вычисления одного кода недостаточно, нужны данные, нужен процессор, нужна память, etc. И для прикладника (правильного прикладника) нить - это более или менее независимая задача от других задач (о параллельности речь может и не идти совсем). При этом, независимость может быть очень разная. Апогей независимости - это процесс, поэтому он никак не может стать нитью, или поднитью, или подподнитью. Наоборот, развязка нитей приблежает их к процессам и даёт возможность, например, приложению работать на нескольких компьютерах. Разделение адресных пространств - это благо.
И програмное распараллеливание никуда не уйдёт. Возможно, оно будет производиться автоматически, но уж точно программным способом. Все современные архитектуры: Cell, VLIW, EDGE, multicell - это упрощение железа за счёт добавления мозгов компилятору и операционной системе.
Общемировой опыт, изложенный, например, в taoup, говорит о том, что это как раз правильные нити превращаются в нечто подобное процессам: взаимодействие через очереди сообщений (аналог pipe'ов или socket'ов) и явная привязка нитей к обрабатываемым общим данным (аналог mmap). Мой собственный опыт разработки чего-то более или менее надёжного и эффективного это подтверждает.
От синхронизации тоже никуда не сбежать. Если файловая система одна, то 10 задач (tasks) работать с ней без синхронизации в каком-либо виде не смогут. Хоть синхронно, хоть (и даже тем более) асинхронно. Поддержка этого всего может быть аппаратной или не аппаратной, но проблемы с потерями производительности на ожидания и со сложностью протоколов взаимодействия она не решит.
Менять надо сам способ описания параллельных программ, а не механизмы поддерживающие работу многозадачных систем. Кстати, в любом современном процессоре есть куча примитивов для поддержки именно многозадачности: начиная с прерываний, режима ядра, специальных инструкций, вроде cmpxchgl, регистров (регистры на самом деле - это именно средства поддержки многозадачности. Существуют процессоры без регистров и на них с многозадачностью довольно туго), заканчивая алгоритмами синхронизации кэшей. Разве этого мало?
Вобщем, затраты на переключение контекста процесса по сравнению с контекстом нити в худшем случае составляют +200 тактов. При этом, затраты на синхронизацию при программировании с нитями и усложнение основных служб ядра операционной системы эти 200 тактов с лихвой перекрывают.
Процессы снимают проблему со стеками и со сборкой мусора, вполне естественным образом: стеки различны, а при завершении процесса все занимаемые ресурсы можно освободить.
Сложность в параллельном программировании упирается не в создание или управление задачами (нитями или процессами), а в сложность описания взаимодействия между ними. Собственно, кажется, в данный момент известно, от куда у этого усложнения по сравнению с обычным программированием ноги растут и работы по исправлению ситуации ведуться. Уточнять не буду, пока статью не опубликую, но желающие могут посмотреть в направлении Linda.
P.S. Маленький вопрос: процессор в 3 гигагерца - это же pentium 4 не самый новый, то есть 32 битный процессор. Если Вы писали под Windows, то для приложения доступное виртуальное адресное пространство составляет 2 гигабайта. А для каждой нити отводится по умолчанию по мегабайту стека, меньшие же стеки опасны, обычно. Как вы умудрились запустить одновременно 10 тысячь нитей, работающих с сетью через динамические библиотеки, требования к объёмам стеков у которых заранее не известны?
В императивном же варианте решения, у меня все данные будут торчать наружу. И я в любой момент смогу начать визуализацию, хоть в параллельном режиме, просто скопировав некоторые данные на stdout или передав их другой нити.
Это можно запроектировать и в объектной модели, но это потребует очень многих размышлений, которые вобщем-то будут не самыми очевидными. А императивное программирование нужные интерфейсы, в конце концов выявит в процессе программирования.
Вот. Конечно, такую задачу можно решить организовав систему обслуживания, с классической MT в центре, которая умножает конкретное число на два. Но вся система уже не будет эквивалентна МТ в строгом смысле. Хотя бы по той причине, что всевозможных случайных величин континуум, а всевозможных лент у любой МТ - счётное количество.
По идее, следующее должно стать очевидным. (1) такая опять же априорная модель разбиеня задачи, которая опирается на понятия, существующие в голове программиста, до анализа решения: стержни очень похожи на стек, следовательно, да будет стек в модели - не полная. Для построения эффективного генератора последовательности ходов, по идее, должен понадобиться объект 'самый мелкий кружочек', который должен будет хранить информацию о предыдущем её перемещении.
(2) Такой алгоритм тоже не сможет начать строительство программы ходов для бесконечной башенки, он будет опираться на значения, записанные в стек, а в стек не влезет бесконечная башенка. Можно, конечно, и тут ООП показывает свою приятную сторону, один из стеков сделать таким, что он никогда не пуст и выдаёт (N + 1), когда выполняется pop, а он пуст.
Но этот подход по сравнению с переписыванием программы, которое (подчеркну) достаточно просто возникает при взгляде на то, какие процессы происходят при перемещении кружочков, и требует чуть больше интеллектуальных усилий, что и рекурсивные построения, будет требовать всё более и более длинные ячейки для хранения элементов стека. То есть, понадобится реализовать ещё один объект: число с переменной длинной. Ещё немного головной боли ОО программисту, imho.
P.S. пример с крестиками и ноликами очень хорош: классическая машина Тьюринга не может сыграть в крестики и нолики, а компьютер может.
Понятия мощность и эквивалентность - обычные из математической логики. Хм... Ну. Так и быть, дам определения:
Мощность - это множество задач, для которых существует алгоритм в рамках этой модели. Чем больше задач во множестве, тем модель мощнее.
Для алгоритмов в разных моделях эквивалентность определяется следующим образом: пусть A и B - преобразования над входом, выполняемые двумя алгоритмами соответсвенно. Пусть алгоритмам на вход могут быть поданы данные из множеств IA и IB, а в результате алгоритмы выдают результаты в виде элементов множеств OA и OB, соответсвенно. Если существуют изморофизмы o: OB -> OA и i: IA -> IB, такие, что o(B(i(x)) = A(x), то алгоритмы A и B называются эквивалентными.
МТ с вводом/выводом - это обычная машина Тьюринга с дополнительными регистрами ввода (вывода), в которых в каждый момент времени может присутствовать один из символов алфавита ленты. А множество комманд такой машины, кроме классических, включает так же в себя комманды вида a, S1 -> get (set), S2, где put означает запись на ленту символа из регистра ввода (чтение с ленты буквы и помещение её в региср вывода).
Понятие вычислимости здесь иное. Считается, что такая машина вычисляет функцию (или уже можно говорить об операторах), если в регистр ввода подаётся последовательность букв, кодирующая input задачи, а на выходе получается последовательность, кодирующая output.
Последовательности потенциально могут быть бесконечными, и это ни сколько не противоречит теоретическим возможностям компьютера: например, очень устойчивая база данных.
Давайте разберёся с этим примером до конца. Итак, теперь у нас три стека и класс game с указанным интерфейсом, что дальше?
http://mikhanoid.habrahabr.ru/blog/13955…
Бесконечное множество МТ с I/O, способные друг другу сообщать о результатах расчётов - не эквивалентны одной такой машине, и обладают огромной вычислительной мощностью.
Возможно, конечно, представить машину с I/O цепочкой классических машин, которые обрабатывают данные друг за дружкой, но эта цепочка должна быть (1) бесконечной, следовательно (2) эта модель не сводится к классической МТ, обладающей лишь конечным числом состояний.
И потом. В обычном компьютере задачи могут во время вычислений обмениваться данными. В классической MT никаких обменов со внешним миром во время работы не предусматривается - это самое важное отличие от машины с вводом/выводом. Это влияет на то, что машина может делать и с какими данными оперировать, и на математические свойства модели (в очередной раз повторяюсь).