Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Перечіслімий безліч



План:


Введення

Не слід плутати з рахунковим безліччю.

В теорії множин, теорії алгоритмів і математичній логіці, Перечіслімий безліч (ефективно Перечіслімий, рекурсивно Перечіслімий, полуразрешімое безліч [1]) - безліч конструктивних об'єктів (наприклад, натуральних чисел), всі елементи якого можуть бути отримані за допомогою деякого алгоритму. Доповнення перечислимого безлічі називається корекурсівно Перечіслімий. [2] Будь-яке Перечіслімий множина є арифметичним. Корекурсівно Перечіслімий безліч може не бути Перечіслімий, але завжди є арифметичним. Перечіслімий безлічі відповідають рівню \ Sigma ^ 0_1 арифметичної ієрархії (англ.), а корекурсівно Перечіслімий - рівню \ Pi ^ 0_1.

Усяке можна розв'язати безліч є Перечіслімий. Перечіслімий множина є розв'язаним, тоді і тільки тоді, коли його доповнення також Перечіслімий. Іншими словами, безліч є розв'язаним в тому і тільки тому випадку, коли воно і Перечіслімий, і корекурсівно Перечіслімий. Підмножина перечислимого безлічі може не бути Перечіслімий (і навіть може не бути арифметичним).

Сукупність усіх Перечіслімий підмножин \ N є рахунковим безліччю, а сукупність всіх неперечіслімих підмножин \ N - незліченною.


1. Варіанти визначення

Різним формалізацію уявлень про алгоритмі відповідають різні формальні визначення поняття перечислимого безлічі, що опиняються еквівалентними. Так, на основі поняття рекурсивної функції Перечіслімий безлічі натуральних чисел можуть бути визначені як образи частково рекурсивних функцій однієї змінної (тому Перечіслімий безлічі натуральних чисел іноді називають "рекурсивно Перечіслімий множинами"). Аналогічно, Перечіслімий безлічі слів в деякому алфавіті A можуть бути введені як безлічі результатів роботи машин Тьюринга із зовнішнім алфавітом A, або як безлічі є словами в алфавіті A результатів роботи нормальних алгоритмів над алфавітом A.

В теорії алгоритмів доводиться твердження про те, що областями значень алгоритмів можуть служити Перечіслімий множини, і тільки вони. Це дозволяє ввести ще один еквівалентний спосіб визначення поняття перечислимого множини. Так, Перечіслімий множинами натуральних чисел можуть вважатися області значень рекурсивних функцій, множинами слів - області застосування машин Тьюринга або нормальних алгоритмів з відповідними алфавітами.


2. Приклади

  • Пусте безліч є Перечіслімий.
  • Будь-яке можна розв'язати безліч (зокрема, будь- кінцеве безліч) є Перечіслімий.
  • Безліч номерів машин Тьюринга, що зупиняються на порожньому вході, також є Перечіслімий (хоча і не є розв'язаним, оскільки його доповнення неперечіслімо).
  • Проекція (англ.) перечислимого множини є Перечіслімий.
  • Об'єднання і перетин кінцевого числа Перечіслімий множин також є Перечіслімий.
  • Безліч натуральних чисел, десяткова запис яких зустрічається в якості підрядка в десяткового запису числа π, є Перечіслімий, а в разі нормальності числа π - навіть вирішуваним тривіальним чином (все безліч натуральних чисел).
  • Безліч раціональних чисел, менших постійної Хайтіна Ω, Перечіслімий, але не вирішується.
  • Але безліч раціональних чисел, великих постійної Хайтіна Ω, неперечіслімо (хоча і аріфметічно і корекурсівно Перечіслімий).
  • Безліч доказових тверджень в арифметиці першого порядку Перечіслімий.
  • Але безліч справжніх тверджень в арифметиці першого порядку не є ні Перечіслімий, ні корекурсівно Перечіслімий (і навіть не є арифметичним, що складає твердження теореми Тарського про невимовність істини в арифметиці).

3. Диофантово

Будь Перечіслімий безліч цілих чисел (або кортежів цілих чисел) має диофантово уявлення, тобто є проекцією безлічі всіх рішень деякого алгебраїчного диофантова рівняння.

Література

  • Роджерс Х. Теорія рекурсивних функцій і ефективна обчислюваності. - М.: Мир, 1972.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Безліч
Безліч
Нескінченна безліч
Канторової безліч
Щільне безліч
Рахункове безліч
Універсальне безліч
Безліч Мандельброта
Безліч Жюліа
© Усі права захищені
написати до нас
Рейтинг@Mail.ru