Подсчет с постоянным ограниченным пространством TMS

Question

Проблема, исходящая от вопроса интервью, заключается в:

У вас есть поток входящих чисел в диапазоне от 0 до 60000, и у вас есть функция, которая займет число из этого диапазона и вернет количество возникновения этого числа до этого момента. Дайте подходящую структуру данных/алгоритм для реализации этой системы.

Поток бесконечен, поэтому, если используются структуры данных фиксированного размера, то есть примитивные типы в Java или C, они будут переполнены. Таким образом, необходимо использовать структуры данных, которые имеют размер, который растет со временем. Как указал интервьюер, память, занятая этими структурами данных, будет расходиться.

Модель вычисления - это машина с тремя лентами:

• Бесконечная односторонняя входная лента только для чтения;
• постоянная космическая счетная записка с двусторонней рабочей лентой;
• Бесконечная выходная лента с односторонней лентой только для записи.

Основная причина выбрать приведенную выше модель заключается в том, что в реальном мире практически нет предела к количеству ввода, которые можно получить с помощью клавиатуры или сетевого соединения. Кроме того, практически нет ограничения в количестве информации, которая может отображаться на Amonitor с течением времени. Но память ограничена и дорогая.

Я смоделировал проблему как проблему, чтобы распознать язык L всех пар (число, количество случаев до сих пор).

В качестве следствия теоремы 3.13 в Hopcroft-Ullman я знаю, что каждый язык, распознаваемый постоянным пространством, является регулярным.

Но, в любой момент, язык L является конечным языком, потому что количество пар, которые нужно распознавать, конечно: 60001. Поэтому я не могу использовать насосную лемму для обычных языков, чтобы доказать, что такой язык не является регулярным.

Есть ли способ завершить свое доказательство?

Первоначальный вопрос здесь.

Answer 1

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

Язык, с которым вы имеете дело, можно определить следующим образом. Пусть $ s in sigma^{ mathbb {n}} $ будет (счетно) бесконечная строка символов из некоторых конечных алфавитов $ sigma $, и пусть $ s [1: i] $ будет префиксом первого $ i $ символы в $ s $. В вашем случае $ s $ - это вход, а $ sigma $ - неотрицательные положительные целые числа $ {0, ldots, 60000 } $. $ L (s) $ можно определить как язык тройков $ (s [1: i], a, j) $, где $ (s [1: i], a, j) in l (s) $ Если и только в случае возникновения $ j $ $ a $ $ s [1: i] $. Уберите себя, используя насосную лемму, что для любой фиксированной $ S $ L (S) $ не является регулярным. Затем убедите себя, что если ограниченная машина для памяти может решить вашу проблему, она также может распознать нерегулярный язык $ l (s) $. Этот аргумент должен работать, даже если мы исправляем $ a $ и определим аналогичный язык $ l (s, a) $.

Эти виды примеров являются причиной, по которой наша вычислительная модель выбора (наше сообщество Algorithms) является словом Ram Machine, и мы предполагаем, что размер слова растет с размером ввода. Предполагается, что это будет моделировать тот факт, что по мере того, как мы сталкиваемся в реальности, и память о наших компьютерах. Конечно, в какой -то момент мы столкнемся с физическими пределами аппаратного обеспечения: есть только так много памяти, к которой можно быстро получить доступ к одному/конечному количеству процессоров. Одним из способов выйти за рамки этих пределов является иерархии памяти, и моделирование становится более сложным, но есть и очень хорошая теория (см. Модели внешней памяти и алгоритмы кеша).

Answer 2

Для простоты предположим, у вас нет 600 000 номеров, но только 1. В какое -то время $ i $ определенное количество 1s были отправлены. Мы называем этот номер префикс потока. Есть бесконечно много возможных префиксов.

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

Я надеюсь, что это убедительно, хотя это не очень формально.