Шумная версия игры жизни Конвея поддерживает универсальные вычисления?

30

Цитируя Википедию , «[Игра Жизни Конвея] обладает мощью универсальной машины Тьюринга: то есть все, что может быть вычислено алгоритмически, может быть вычислено в Игре Жизни Конвея».

Распространяются ли такие результаты на шумные версии игры жизни Конвея? Простейшая версия состоит в том, что после каждого раунда каждая живая клетка умирает с малой вероятностью а каждая мертвая клетка становится живой с малой вероятностью (независимо). $t$ $s$

Другой возможностью является рассмотрение следующего вероятностного варианта правила самой игры.

Любая живая клетка с менее чем двумя живыми соседями умирает с вероятностью . $1-t$
Любая живая клетка с двумя или тремя живыми соседями живет с вероятностью для следующего поколения. $1-t$
Любая живая клетка с более чем тремя живыми соседями умирает с вероятностью . $1-t$
Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой с вероятностью . $1-t$

Вопрос: Поддерживают ли эти шумные версии Game of Life универсальные вычисления? Если нет, что можно сказать об их «вычислительной мощности»?

Также будет высоко оценена соответствующая информация о вычислительной мощности клеточных автоматов и зашумленных версиях клеточных автоматов.

(Этот вопрос возник из этого вопроса о MathOverflow. Ответ Винсента Беффары на МО дал интересные ссылки на связанные результаты по вычислительным аспектам шумных клеточных автоматов.)

cc.complexity-theory pr.probability cellular-automata fault-tolerance Гил Калай
источник

2

@vzn 1) нет, это не "реальный вопрос", это совершенно другой вопрос; Вопрос Гила касается устойчивости простой вычислительной модели к шуму, а не силы случайности; 2) ТМ со случайной лентой не более мощны, чем детерминированные ТМ, см. Этот ответ: cstheory.stackexchange.com/a/1415/4896

Сашо Николов

2

Реальный вопрос здесь в том, стохастические / шумные версии «Игры Жизни» все еще поддерживают вычисления. (Если эти версии поддерживают вычисления в P, то их мощность может доходить до BPP.) Возможно, вычислительная мощность этих стохастических версий игры жизни намного ниже.

Гил Калай

3

Возможно, я утверждаю очевидное, но вы можете просто продублировать конфигурацию достаточно много раз, чтобы с высокой вероятностью гарантировать, что в версии конфигурации даже не будет перевернута одна ячейка. Мое личное убеждение в том, что мы можем сделать намного лучше, но, по крайней мере, это простая нижняя граница.

user834

4

Я не уверен, что вопрос четко определен. Предположим, что

. Мне кажется, что вы, возможно, сможете найти компьютер, который обрабатывает все однобитовые ошибки в «Игре жизни», предоставляя вам отказоустойчивые вычисления, если вы спонтанно не получаете большой блок ошибок сразу. Но я не думаю, что что-то может быть надежным против всех ошибок. Например, предположим, что ошибки спонтанно создают злонамеренного противника, решившего нарушить вычисления. Вы могли бы показать, что ваши вычисления успешны с вероятностью

но с ошибкой

. Это считается?

t = 10^{- 9}

$t=10^{−9}$

> 1 - 10^{- 9}

$>1−10^{−9}$

> 10^{- 10000}

$>10^{−10000}$

Питер Шор

2

Питер, если твои вычисления пройдут с вероятностью 2/3, я счастлив.

Гил Калай

8

Вот несколько «лучших» ссылок, которые того стоят. Казалось бы, путь к этому вопросу состоит в том, чтобы свести его к вопросу о «шумных машинах Тьюринга», которые были изучены (несколько недавно) и которые, по-видимому, являются ближайшей соответствующей областью литературы. Основной / общий / разумный ответ, по-видимому, заключается в том, что, если ТМ может сопротивляться / исправлять шум (как показано в этих ссылках), вполне вероятно, что ЦС также может, в пределах некоторых границ / порогов.

Вопрос о том, как уменьшить «шумный ЦС» до «шумного ТМ» (и наоборот), более открыт. Это может быть не сложно, но, похоже, не опубликовано исследований в этой области. Другая проблема заключается в том, что зашумленная ТМ - это новая модель, и поэтому может быть несколько (естественных?) Способов представления зашумленной ТМ. Например, в следующих статьях рассматриваются сбои в функции перехода состояний, но другая естественная модель - это сбои в символах ленты (последние более связаны с шумными ЦС?). Там может быть некоторая связь между ними.

Отказоустойчивая машина Тьюринга от Ilir Capuni, 2012 (кандидатская диссертация)

Машина Тьюринга является наиболее изученной универсальной моделью вычислений. Этот тезис исследует вопрос, существует ли машина Тьюринга, которая может надежно вычислять, даже когда нарушения ее переходной функции происходят независимо друг от друга с некоторой малой вероятностью.

В этом тезисе мы доказываем существование машины Тьюринга, которая с полиномиальными издержками может моделировать любую другую машину Тьюринга, даже если она подвержена сбоям вышеупомянутого типа, тем самым отвечая на вопрос, который был открыт в течение 25 лет.
Машина Тьюринга, противостоящая изолированным вспышкам неисправностей. Автор Ilir Capuni и Peter Gacs, 2012
Шумные машины Тьюринга. Автор: Евгений Асарин и Питер Коллинз, 2005

(Другой вопрос: может ли быть какая-то связь между шумными ТМ и вероятностными машинами Тьюринга ?)

ВЗН
источник

7

Гил спрашивает, не забывает ли GL все о своей начальной конфигурации во времени, не зависящем от размера, когда каждая ячейка «не подчиняется» функции перехода независимо от других ячеек с некоторой малой вероятностью.

Насколько мне известно, это не известно для GL. Это очень интересный вопрос. Если он может противостоять шуму, то он должен сохранить свою универсальность.

Краткий обзор современного уровня техники заключается в следующем.

Правило Тоома может сохранить один бит навсегда неисправностей, которые происходят независимо друг от друга с некоторой малой вероятностью.
Широко распространено мнение (гипотеза положительных скоростей), что все 1 dim CA являются эргодическими, пока P. Gacs не построил свой многомасштабный CA, который может моделировать любой другой CA с умеренными накладными расходами, даже когда подвергается вышеупомянутому шуму.
Вопрос о том, может ли правило G (acs) K (urdiumov) L (evin) сохранить один бит навсегда при наличии вышеуказанного шума, остается открытым. Kihong Park - студент Gacs - показал, что это не так, когда шум предвзят.
Когда работа в 2 была опубликована, М. Блум спросил, может ли ТМ продолжить свои вычисления, если на каждом шаге переход не выполняется согласно функции перехода с некоторой малой вероятностью независимо от других шагов, предполагая, что информация, хранящаяся на лента далеко от головы не гниет. Положительный ответ дал И. Капуни (еще один студент Gacs) в 2012 году.

user8719
источник

«Если оно не эргодично, то оно сохранит свою универсальность» ... есть ли у вас доказательства этого утверждения? Это теорема? Где это доказано? Я полагаю, что работа Гакса показывает, что это верно по крайней мере в одном случае, но я не вижу, как это доказывает, что это применимо к игре Конвея о жизни.

Питер Шор

Спасибо за указание. Это не теорема, а интересный открытый вопрос. Не быть эргодичным, кажется, слишком мало, чтобы просить о таком сильном утверждении.

user8719

3

Для начала имейте в виду, что исследования в игре «Жизнь жизни» Конвея все еще продолжаются, и будущие разработки могут представлять собой гораздо менее сложное решение.

Сейчас, когда. Интересно, что эта тема на самом деле соответствует биологии и квантовой физике так же, как и традиционной компьютерной науке. Суть вопроса в том, может ли какое-либо устройство эффективно противостоять случайным изменениям своего состояния. Ответ прост и понятен: невозможно создать такую машину, которая идеальноустойчив к таким случайным изменениям. Конечно, это верно во многом так же, как квантовая механика могла вызвать, казалось бы, невозможные события. То, что препятствует тому, чтобы эти события произошли (ведущий большинство людей объявить их строго невозможными), является невероятно маленькой вероятностью, что такое событие имеет место. Вероятность, сделанная настолько малой из-за большой разницы между квантовым уровнем и уровнем человека. Аналогичным образом можно создать конечный автомат, устойчивый к малым степеням случайных изменений, просто сделав его настолько большим и избыточным, что любое замеченное «изменение» фактически равно нулю, но предполагается, что это не является целью. Предполагая, что это может быть достигнуто так же, как животные и растения устойчивы к радиации или физическим повреждениям.

В таком случае вопрос может заключаться не в том, как предотвратить низкоуровневые помехи от нанесения слишком большого ущерба, а скорее в том, как оправиться от максимально возможного ущерба. Здесь биология становится актуальной. Животные и растения на самом деле обладают этой самой способностью на клеточном уровне (обратите внимание: я говорю о клетках в биологическом смысле в этом ответе). Теперь, в игре жизни Конвея, идея создания вычислительного устройства в масштабе отдельных клеток это привлекательно (в конце концов, это делает такие создания намного меньше и эффективнее), но хотя мы можем создавать самовоспроизводящиеся компьютеры ( см. Близнецы ), это игнорирует тот факт, что сам объект-конструктор может быть поврежден возмущениями.

Другой, более устойчивый способ решения этой проблемы - создание компьютеров из самовоспроизводящихся избыточных частей (например, биологических клеток), которые выполняют свои операции, воспроизводят и заменяются.

В этот момент мы можем увидеть еще одну интересную параллель реального мира. Эти низкоуровневые помехи сродни воздействию радиации. Это наиболее заметно, если учесть тип повреждения, которое может быть нанесено вашим клеточным автоматам. Легко вызвать сбой каскада или «смерть» клетки в игре жизни Конвея, почти так же, как это происходит со многими клетками, подвергающимися воздействию радиации. Но существует наихудшая возможность мутации, в результате которой создается «раковая» клетка, которая продолжает воспроизводить свои поврежденные копии, которые не помогают в вычислительном процессе или дают неверные результаты.

Как я уже говорил, невозможно создать систему, которая полностью защищена от ошибок, вы можете только снизить вероятность того, что система скомпрометирует всю систему. Конечно, фундаментальный вопрос здесь действительно заключается в том, «являются ли вероятностное моделирование самим по Тьюрингу полным», что уже было решено, чтобы быть правдой . Сначала я бы ответил на этот фундаментальный вопрос, если бы не тот вопрос, который вы задали.

Ястребиное Крыло
источник

Вот Это Да! Спасибо за езду вниз! Во всяком случае, я пересмотрел свой пост, добавив некоторую информацию и источники. Извините, у меня не было времени сделать это, когда я впервые опубликовал это. Я мог бы изменить этот ответ еще больше, чтобы он соответствовал стандартам сообщества, если бы не тот факт, что не было дано никаких оснований для понижения голосов.

Hawkwing

5

Как не голосующий, я не понимаю, как это отвечает на вопрос Гила. Вы обращаетесь к вопросу о том, «может ли какое-либо устройство эффективно противостоять случайным изменениям его состояния», - это не то, что спросил Гил.

Андрас Саламон

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

Hawkwing

0

Мне напомнили о xkcd 505: куча камней .

Любой реальный компьютер подвержен некоторому уровню шума. Имитация универсального компьютера в идеальной бесконечной вселенной Жизни Конвея будет иметь среднее время между отказами в зависимости от технических деталей его конструкции. Он будет надежно вычисляться в течение вероятностно измеряемого периода, ненадежно в течение периода накопления ошибок, а затем и вовсе не будет .

Я ожидал бы, что нечеткая логика или модель квантовой суперпозиции ясно продемонстрируют, какую надежность следует ожидать от конкретной конструкции. Можно хотеть смоделировать ожидаемые выходные данные различных компонентов, а не выполнять итерацию по всем их ячейкам, в какой бы степени они не были изолированы друг от друга. Можно было бы определить количество ожидаемых помех от неисправных компонентов. Генетический алгоритм должен быть наилучшим способом разработки отказоустойчивых, сопротивляющихся, исправляющих компонентов с MTBF, настолько большими, насколько это необходимо для данного распределения шума.

user130144
источник

(загадочное голосование здесь) Количественный ответ был бы очень умозрительным. Не может быть более точного ответа, чем «да, условно», без обширных экспериментов с какой-то выбранной реализацией UTM. Нормальный компьютер в условиях высокой радиации до сих пор практически УТМ, если только кратко.

user130144

Шумная версия игры жизни Конвея поддерживает универсальные вычисления?

Ответы: