XDiaBLo tchingiz
вот программа на языке sql для построение множества {0, 1}:

Может не dummy, а dual? dummy там поле называется, а не таблица.
dual - там, в оракле,
а там, в сайбесе - dummy

Gluk (Kazan) tchingizя могу записать программу для генерации мощности 3 {0,1,2}

но это уже другая программа, а нужна одна и та же.

я приводил ссылку :


можно до хрипоты спорить, кошерный SQL это или нет, но ведь точно также можно спорить и о Бейсике, мотивируя некошерность, скажем, VBA тем, что с GW-бейсиком оно не имеет ничего общего :) Жизнь идет, ярлыки перевешивают

Единственное о чем я беспокоюсь - хватит ли всего 2 ярлыков для описания всего многообразия языков программирования ?

вполне может не хватить.
Я же забыл о важности доказательства по тексту функциональной программы.
собственно по ссылке:
>>До меня тут доехало, что с введением CTE
>>(common table expressions) язык SQL стал тьюринг-полным.
то есть, не только я не мог сгенерировать потенциально бесконечное множество на sql-е из 6 главы монографии Дейта, а и разработчики и пользователя Firebird-а. повидимому это невозможно. Введение требуемой аксиомы цикла в диалект отражает частую необходимость
работы с потенциально бесконечным множеством.

я продолжаю исходить из предположения
автор
Без тени лукавства, хочется понять Вашу логику

Gluk (Kazan) tchingizВаш пример с тремя точками - не годится - это символ.
нужна "не изменяемая потом процедура" котороя будет строить это множество целиком.


a{0,$N}b

Cтроит (или распознает если угодно) потенциально бесконечное множество строк. Т.е. по Вашей классификации, язык регулярных выражений относится ко второй группе (кстати не поддерживая при этом рекурии или каких-либо императивных циклических конструкций). Классификация языков вполне себе не хуже любой другой. Но адекватна ли она ???

эта цепочка не строит. Это определение того, что такая цепочка a{0,$N}b распознает бесконечное множество цепочек {b, ab, aab, ...}.
наверно, ее можно интерпретировать как предикат a{0,$N}b : string -> bool

Вы, судя по всему, в определении(в аксиоматике) уже договорились, что эта цепочка означает ВСЕ, то есть, постулировали существование готового бесконечно большого множество сразу. Квантор всеобщности использовали в постулате.

позволю себе напомнить аксиоматику Пеано


автор
-
scheme PEANO =
class
type -- завели тип N
N
value
zero : N, -- завели величину zero
-- (это не переменная, нельзя присваивать)
succ: N -> N -- величина - функция из N в N
axiom
[first_is_zero] --
-- квантор всеобщности
all n : N :- -- n - это обозначение

~(succ(n) is zero) -- для каждого n результат succ(n)
, -- не есть zero
[linear_order]
all n1, n2 : N :-
(succ(n1) is succ(n2)) => (n1 is n2)
,
[induction]
all p : N -> Bool :- -- для любого предиката
--
(p(zero) /\ (all n : N :- p(n) => p(succ(n))))
=>
(all n : N :- p(n))
end

--
-- ~ отрицание
-- :- выполняется
-- => влечет
-- /\ логическое и
-- \/ логическое или
-- exist квантор существования
-- all квантор всеобщности
--


постулируется существование нуля - zero,
и функции инкремента succ,
то есть 1 это succ(0)
2 это succ(succ(0))
...
дополнительно явно выводится что 2 не равно 1 и не равно 0;
3 не равно 2 и не равно 1;
4 не равно 3 не равно 2 и не равно 1;
...

квантор всеобщности появляется ТОЛЬКО В АКСИОМЕ ИНДУКЦИИ.


пусть N- множество натуральных чисел, предикат p - это утверждение "для некоторого n можно записать цепочку состоящую из n раз взятых а и последующей б".
Утверждение all n: N :- p(n) это уже другое утверждение.
справедливость утверждения с квантором не проверябельна (можно проверить для одного, пяти, ста, но нельзя проверить для всех). А следует из постулата о справедливости матиндукции.

не строит a{0,$N}b бесконечное множество цепочек, а - обозначает, ограничивает или
извлекает (распознает) из другого бесконечного множества.

и вполне может интерпретироваться как язык запросов.

то эта цепочка означает ВСЕ

читать как
то эта цепочка означает ВСЕ строчки удовлетворяющие тому то

Gluk (Kazan) XDiaBLo Gluk (Kazan) XDiaBLo Gluk (Kazan) XDiaBLoесли нельзя написать программу, то не язык программирования.

а что такое программа ?

Компью́терная програ́мма — последовательность формализованных инструкций, предназначенная для исполнения устройством управления вычислительной машины.
Только при эдаком объяснении не только SQL но и HTML получается язык программирования... Тьфу.

дурное определение. ФП под него не попадает. Где там последовательность инструкций ???
Ну есть же там какие-то инструкции в функциях?

Ага, только нет последовательности инструкций (в общем случае)
Взять к примеру Prolog. Определенная интерактивность внутри правил выводы в нем еще осталась,
но назвать программу на Prolog-е последовательностью инструкций (у меня лично) язык не повернется.

почему?

XDiaBLo tchingizграмматика языка sql может быть описана на yacc-е ( я сам это видел в примерах по yacc),
то есть, sql является контекстно независимым (контекстно свободным) языком
Но при этом как ни странно он считается не языком программирования, а языком запросов.


create table foo(
a integer;
)

select 1 from foo -


Integer-set - это множество всех подмножества множества Integer.

это программа, реализующая фукцию f: Integer-set -> {1}

select sum(*) from foo
программа, реализующая функцию power: Integer-set -> Unsigned Integer

Gluk (Kazan)

Ага. а можно как Integer -> [String]
Строит или распознает - это уже схоластика.
По мне так регулярное выражение определяет язык (т.е. множество возможных цепочек на заданном алфавите)
да. а восьмерка на боку определяет (постулирует) бесконечное множество.
утверждая, что оно есть.
я и говорю, что Ваше выражение a*b это такой же символ для обозначения бесконечного множества специального вида.

"распознает" - я в математике не помню такого термина.
интуитивно могу его представить как предикат p : String >< String -> Bool
первая строчка интерпретируется как регулярное выражение, вторая как строка.
разспознала (похожа) выдали true, иначе false.
или как метрику на множестве строчек - далеко ушло регулярно.

grep вполне сойдет на аналог rdbms,
grep ab file == select * from table where field like '%ab%'

как извлечь a*b в сайбейсе не нашел. ))
похоже a* обладает свойствами цикла

вот c127 занятно реализовал регулярное выражение на sql