Користувач:Rililinx/Принцип Маркова
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Maquina.png/250px-Maquina.png)
Принцип Маркова, названий на честь Андрія Маркова-молодшого, є принцом умовного існування, що має багато формулювань.
Принцип класично доводиться, але не за допомогою конструктивної логики Але для багатьох конкретних випадків цей принцип все ж можна довести використовуючи обидві логики.
Вперше принцип був запропонований російською школою конструктивізму разом із аксіомами залежного вибору та часто використовувался для перевірки існування математичної функції.
На мові теорії обчислюваності принцип Маркова формально стверджує, що якщо неможливо, щоб алгоритм зупинявся, то для деяких вхідних даних він зупиниться. Це еквівалентно твердженню, що якщо множна і її доповнення є перерахованою множиною, то множина є обчислюваною.
У логіці предикатів: предикат P над деякою множиною називається обчислювальним, якщо для кожного x в множини або P ( x ) є істинним, або P ( x ) не є істинним.
Для обчислювального предикату P над натуральними числами принцип Маркова звучить так:
Тобто, якщо предикат P не є хибним для всіх натуральних чисел n, то він є істинним для деяких n .
Правило Маркова — це формулювання принципу Маркова як правила. Воно стеверждує, що можна отримати, тільки якщо виконується для . Формально,
Якщо використовувати мову математичного аналізу, то принцип Маркова можно сформулювати так:
де - обчислювальна функція на натуральних числах.
Принцип Маркова можно сформулювати використовуючи аналіз функції дійсної змінної
- Якщо для кожного дійсного числа x, твердження, що x дорівнює 0 є хибним, то існує y ∈ Q таке, що 0 < y < | x |
- Якщо для кожного дійсного числа x, твердження, що x дорівнює 0 є хибним, то існує y ∈ R такий, що x*y = 1.
Слабкий принцип Маркова — це слабша форма принципу Маркова, яку мовою аналізу можна висловити як
Це умовне твердження про обчислювальність позитивності дійсного числа.
[[Категорія:Математичні принципи]] [[Категорія:Логіка]]