Как я могу реализовать бесконечный класс?

Ответ 1

Невозможно полностью реализовать ISet<T> для несчетно бесконечных множеств.

Здесь доказательство (любезно предоставлено Бертран Расселом):

Предположим, вы создали класс MySet<T>, который может представлять несчетно бесконечный набор. Теперь рассмотрим некоторые объекты MySet<object>.

Мы отмечаем конкретный MySet<object>, называем его instance, "ненормальным", если:

instance.Contains(instance) возвращает true.

Аналогично, мы бы обозначили instance как "нормальный", если:

instance.Contains(instance) возвращает false.

Обратите внимание, что это различие хорошо определено для всех instance.

Теперь рассмотрим экземпляр MySet<MySet<object>>, называемый paradox.

Определим paradox как MySet<MySet<object>>, который содержит все возможные нормальные экземпляры MySet<object>.

Что следует вернуть paradox.Contains(paradox)?

Если он возвращает true, то paradox является ненормальным и должен возвращать false при вызове сам по себе.

Если он возвращает false, тогда paradox является нормальным и должен возвращать true при вызове сам по себе.

Невозможно реализовать Contains для решения этого парадокса, поэтому нет возможности полностью реализовать ISet<T> для всех возможных несчетных множеств.

Теперь, если вы ограничиваете мощность MySet<T> равным или меньшим, чем мощность континуума (| R |), вы сможете обойти этот парадокс.

Даже тогда вы не сможете реализовать Contains или подобные методы, потому что это будет эквивалентно решению проблемы остановки. (Помните, что набор всех программ C# имеет мощность, равную | Z | < | R |.)

ИЗМЕНИТЬ

Чтобы быть более основательным, объясните мое утверждение, что "это будет равносильно решению проблемы остановки".

Рассмотрим MySet<string>, который состоит из всех программ С# (как строк), которые останавливаются за конечное время (предположим, что они останавливаются для любого ввода, если быть точным). Назовите его paradox2. Множество * рекурсивно перечислимо ", что означает, что вы можете реализовать GetEnumerator на нем (не так просто, но это возможно). Это также означает, что он хорошо определен. Однако этот набор не является" разрешимым ", поскольку его дополнение не рекурсивно перечислимый.

Определите программу С# следующим образом:

using ... //Everything;

public static class Decider {

    private MySet<string> _haltingSet = CreateHaltingSet();

    static void Main(string [] args) {
        Console.WriteLine(_haltingSet.Contains(args[0]));
    }
}

Скомпилируйте указанную выше программу и передайте ее как входной для себя. Что происходит?

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

Возможно, вы сможете ограничить класс MySet<T> для работы для всех разрешимых наборов. Однако тогда вы все равно столкнетесь со всеми видами проблем с вашей функцией никогда не останавливается в течение конечного времени.

В качестве примера предположим, что мы имеем вещественный тип точности точности, называемый Real, и пусть nonHalting является экземпляром MySet<Real>, который включает в себя все нетривиальные нули функции дзета Римана (это разрешимый набор). Если вы можете правильно реализовать IsProperSubsetOf на nonHalting для возврата в течение конечного времени, когда передано множество всех комплексных чисел с вещественной частью 1/2 (также разрешимым набором), то вы выиграете Премия тысячелетия.

Ответ 2

Вам нужно будет обобщить то, что вы подразумеваете под Set.

Если у вас будет бесконечный набор, вы не сможете получить значимое перечисление по нему, поэтому вы не будете определять операции с операциями над перечислениями.

Если вы определяете Set<f> в терминах метода bool IsMember(f obj), его можно использовать для бесконечных множеств.

Вы определяете объединение или пересечение двух наборов в качестве логического и/или из метода IsMember для двух наборов.

Ответ 3

представляют несчетно бесконечные множества

Давайте рассмотрим это утверждение в контексте того, как это делается на практике. Например, при задании погоды множество A является подмножеством множества Z (положительные целые числа), объект не является Z. Каждое число в Z не анализируется. То, что анализируется, является рассматриваемым множеством A. Поскольку нет никакого способа сравнить Ak (A sub k, где k - число между 1 и | A |) до каждого значения Z (бесконечное), каждое значение A должно быть по сравнению со свойствами, которые составляют Z. Если каждое значение в удовлетворяет свойствам Z, то A является подмножеством Z.

как вы можете представить в коде R union N

Тот же процесс, что и выше. Свойства R являются "любым реальным числом" - в коде это может быть "любой двойной, который не генерирует исключение" (очевидно, Math.Pow(-1,.5) даст проблемы и не будет в R в результате). Свойства N являются "любым целым числом" - в коде это может быть любое число, где Math.Floor!= Math.Ceiling. Объединение этих двух является объединением их свойств. Любое число, которое придерживается свойств R или N - в коде, было бы любым числом, которое не генерирует исключение для создания или, которое Math.Floor!= Math.Ceiling.

Резюме

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

правки

N ⊆ R?

Давайте вернемся к идее свойств, так как это тема, которую я бы преследовал. Является ли N подмножеством R? Для того чтобы N было подмножеством R, свойства N должны удовлетворять всем свойствам R. Список свойств должен быть точным. Чтобы представить числовое значение бесконечности, я бы предложил использовать класс, который содержит нулевое число int и обычный знак int.

public class Infinite
{
 public int? Number { get; set; }
 public int Sign { get; set; }
}

Что-то в этом роде. Number.Value == null означает бесконечность. Знак можно использовать для отображения отрицательных (-1), + - (0) или положительных (1).

Вернемся к N подмножествам ситуации R. Помимо свойств, перечисленных ранее, N также имеет Infinite.Number == null и Infinite.Sign == 0 в качестве границ для своих свойств. Как и R. Итак, N сможет удовлетворить граничному свойству. Далее будут указаны свойства, определенные выше. Я действительно застрял здесь. Я не уверен, как доказать в коде, что каждое число, которое .Floor ==.Ceiling не вызовет исключения. Однако, поскольку существует только 9 из этих типов суперсетей (Rational, Irrational, Integer, Real, Complex, Imaginary, Transcendental, Algebraic, Natural), вы могли бы специально определить их взаимодействия на бесконечной шкале, а затем использовать более простую реализацию для конечных сравнения.

Ответ 4

Что именно вы собираетесь с этим делать. Вы не можете перечислить его.

Я думаю, что я отношусь к нему как к потомку универсального набора.

Я думаю, что начну с другого конца.

Определите универсальный набор, где Исмембер всегда прав Затем потомок, где IsMember истинно, если оно представляет собой натуральное число {1,2,3,4} является еще одним ограничением N

В любом случае мысль

Ответ 5

Это возможно с большим количеством ограничений, точно так же, как с символическим выражением.

Вот небольшой пример:

class IntSet
{
    int m_first;
    int m_delta;

    public IntSet(int first, int delta)
    {
        m_first = first;
        m_delta = delta;
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();

        sb.Append('[');
        sb.Append(m_first);
        sb.Append(',');
        sb.Append(m_first + m_delta);
        sb.Append(',');
        sb.Append("...");
        sb.Append(']');

        return sb.ToString();
    }

    public IEnumerable<int> GetNumbers()
    {
        yield return m_first;

        int next = m_first;

        while (true)
        {
            next += m_delta;

            yield return next;
        }
    }
}