Публикации по теме 'proof'
Доказательство того, что проблема остановки неразрешима (для программистов-непрофессионалов)
Есть задачи, которые вычислительно невозможны. Они относятся к классу неразрешимых задач. Для неразрешимой задачи не существует алгоритма, который решает задачу на каждом входе независимо от времени работы алгоритма. Вы запускаете полиномиальное время, экспоненциальное время; нет алгоритма, который собирался бы решить это на каждом входе.
В 1936 году великий Алан Тьюринг доказал, что проблема остановки неразрешима. И мы увидим идею этого результата сейчас. Эта статья Тьюринга в..
Вопросы по теме 'proof'
Показывать битовые строки со значением count (1s) = count (0s) нерегулярно
Пусть L - язык, состоящий из строк в алфавите {0,1}, содержащих равное количество единиц и нулей.
Например:
000111
10010011
10
1010101010
Как вы можете показать, что L не является обычным языком?
1121 просмотров
schedule
06.09.2021
Как я могу привязать схематическую переменную? Case к правилу для доказательства по делам?
Я хотел бы определить правило доказательства по делам, которое будет использоваться с proof (cases rule: <rule-name>) . Мне удалось использовать параметры case_names и consumes , но мне не удалось связать схемную переменную ?case , так что...
393 просмотров
schedule
24.10.2021
Доказательство законов функторов для свободных монад; я правильно делаю?
Мне сложно понять, как доказать законы Functor и Monad для бесплатных монад. Во-первых, позвольте мне привести определения, которые я использую:
data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Functor (Free f) where...
618 просмотров
schedule
16.10.2021
Сложность доказательства для рекурсивной функции
Я пытаюсь определить сложность этой функции, где D и element - целые числа, а list - это упорядоченный список целых чисел. Обратите внимание на то, что (otherElement-element) будет строго положительным.
def doFunc(element, D, list):
x = 0...
72 просмотров
schedule
12.09.2021
Есть ли доказательство того, что runST действительно чист?
ST-монада , изначально разработанный Launchbury and Peyton Jones , позволяет программистам Haskell писать императивный код (с изменяемым переменные, массивы и т. д.) при получении чистого интерфейса для этого кода.
Более конкретно, полиморфный...
493 просмотров
schedule
09.11.2021
Не удается применить определение программы из-за невозможности объединить опору с [цель]
В Coq я показал ассоциативность append на векторах, используя:
Require Import Coq.Vectors.VectorDef Omega.
Program Definition t_app_assoc v p q r (a : t v p) (b : t v q) (c : t v r) :=
append (append a b) c = append a (append b c).
Next...
537 просмотров
schedule
08.10.2021
Где найти ресурсы / информацию о контроле доказательств в Prolog
В рамках задания меня попросили проверить правильность или неправильность доказательств естественного вывода с помощью Пролога. Пример текстового файла с именем «valid.txt», содержащего доказательство, выглядит следующим образом:
[imp(p, q), p]....
365 просмотров
schedule
11.09.2021
Если Идрис думает, что все, что не так, может быть полным, может ли Идрис использоваться для доказательства?
http://docs.idris-lang.org/en/v0.99/tutorial/theorems.html#totality-checking-issues указано, что:
Во-вторых, в текущей реализации пока что прилагались ограниченные усилия, поэтому все еще могут быть случаи, когда она считает, что функция...
239 просмотров
schedule
03.03.2022
Автоматизация доказательства в Coq как факторизовать доказательство
Я слежу за книгой Software Foundation и нахожусь в главе под названием «Бес».
Авторы разоблачают небольшой язык, а именно:
Inductive aexp : Type :=
| ANum : nat -> aexp
| APlus : aexp -> aexp -> aexp
| AMinus : aexp -> aexp...
169 просмотров
schedule
05.03.2022
Доказательство пользовательских двоичных строк
Фибоначчи определяется рекурсивно для этого вопроса как: F~0 = 1 F~1 = 1 F~n = F~n-1 + F~n-2 для n >= 2 Таким образом, пользовательская двоичная строка всегда начинается с 1 и никогда имеет два последовательных. Если s = s~Ls~L-1...s~1 является...
163 просмотров
schedule
12.03.2022
Доказательство еще одного свойства нахождения одинаковых элементов в списках
Следуя моему вопросу здесь , я есть функция findshare , которая находит одинаковые элементы в двух списках. Собственно, keepnotEmpty - это та лемма, которая мне нужна в моей программе после внесения некоторых изменений в первоначальную версию...
73 просмотров
schedule
12.03.2022
Используя Omega для доказательства леммы в Coq
Я пытаюсь сделать доказательство в Coq с помощью Omega. Я потратил на это много времени, но мне ничего не пришло. Я должен сказать, что я новичок в Coq, поэтому мне не нравится этот язык, и у меня нет большого опыта. Но я работаю над этим.
Вот...
803 просмотров
schedule
22.03.2022
Доказательство OCaml методом структурной индукции
Учитывая следующую функцию:
let rec foo l1 l2 =
match (l1,l2) with
([],ys) -> ys
| (x::xs,ys) -> foo xs (x::ys))
Докажите следующее свойство:
foo (foo xs ys) zs = foo ys (xs@zs)
Пока что я завершил базовый...
408 просмотров
schedule
27.03.2022
Доказательство индукции $T(n) = 9T(n/3) + n^2$
Как я могу доказать, что повторение
Т(n) = 9T(n/3) + n 2
приводит к T(n) = O(n 2 log(n)) с использованием метода подстановки и доказательства по индукции? Мне не разрешено использовать основную теорему.
Используя индукцию и...
2475 просмотров
schedule
28.03.2022
Доказательство теорем: как оптимизировать обратный поиск доказательства, содержащий бесполезное правило И
Быстрый просмотр:
Правило вывода = заключение + правило + посылки
Дерево доказательств = заключение + правило + поддеревья
Обратный поиск доказательств: с учетом входной цели попробуйте построить дерево доказательств, применяя правила...
102 просмотров
schedule
01.04.2022
Помощник по доказательству только по математике
Большинство помощников по доказательству - это функциональные языки программирования с зависимыми типами. Они могут проверять программы / алгоритмы. Вместо этого меня интересует помощник по доказательству, который лучше всего подходит для математики...
854 просмотров
schedule
09.04.2022
Доказательство через количество шагов вывода
Даны G = {a, b, c, d}, {S, X, Y}, S, {S->XY, X->aXb, X->ab, Y->cYd, Y->cY, Y ->кд}}
Докажите, что |w|c-|w|d+|w|a≥|w|b
|w|a — это количество букв «a» в строке. Это имеет смысл, так как будет больше (или такое же количество) 'c', чем 'd',...
55 просмотров
schedule
26.04.2022
Докажите алгоритм планирования для одной общей машины и одной с бесконечной параллельной мощностью
Вот проблема: все части p_i должны быть обработаны на одной общей машине, а затем части будут очищены один раз другими машинами. Общая машина может обрабатывать только одну деталь за раз. Машина (машины) переработки может обрабатывать неограниченное...
66 просмотров
schedule
24.04.2022
Доказательство рекурсивного алгоритма
Мне нужно доказать рекурсивный алгоритм. Обычно это делается с использованием некоторого целочисленного значения в коде в качестве базового случая для индукции, например, при вычислении факториала, но при обходе графа я не знаю, с чего начать. Вот...
187 просмотров
schedule
29.04.2022
Стабильная сортировка сравнением со временем O(n * log(n)) и пространственной сложностью O(1)
Просматривая список алгоритмов сортировки в Википедии , я заметил, что не существует стабильного сравнительная сортировка со сложностью времени O(n*log(n)) (наихудший случай) и O(1) (наихудший случай) case) пространственная сложность. Это,...
2027 просмотров
schedule
11.05.2022
