IANAL, TINLA.
> Допустим, я разрабатываю техническую спецификацию алгоритма и указываю лицензию CC-BY-SA.
Не могу это назвать хорошим выбором. Зачем? Почему?
> 1. Под какой лицензией нужно публиковать программу, которая реализует данную спецификацию и алгоритм?
Вопрос сложнее, чем вам кажется. Даже если сейчас вы сумеете разрешить все *свои* сомнения, не думаете же вы, что вы тут самый недалекий, и что точно таких же сомнений не возникнет у других? ;-)
> 2. Является ли программа, реализующая данную спецификацию, производной (по условиям CC-BY-SA)?
Это, очевидно, подвопрос к первому.
> 3. Разрешено ли лицензией CC-BY-SA публиковать программу под лицензией Apache?
Нет.
> 4. Стоит ли изменить лицензию спецификации на CC-BY?
Ну я же не знаю, какова ваша цель. Из каких соображений вы выбираете условия для своей свободной спецификации?
Вы хотите поощрить написание по ней программ (свободных или несвободных, не суть)? В таком случае, наверное, не надо обнародовать ее на условиях для фотографий и прочей музычки?
Если же напротив, вам по тем или иным причинам хочется всячески затруднить воплощение вашей спецификации при том, что формально она останется свободной? Тогда конечно, выбирайте типовые лицензии «Креатив-коммонса».
> Насколько я понял программы не рекомендуется публиковать под лицензиями CC.
Совершенно справедливо. [0]
> Там написано, что CC-BY-SA совместима в одну сторону с GPLv3.
Во-первых, есть целый зоопарк лицензий CC BY-SA. Пять, кажется, штук, не считая десятков местных вариантов. Совершенно точно, что четыре из них несовместимы.
Тот же самый зоопарк присущ и CC BY, не надо думать, что он весь с чем бы-то ни было совместим. Даже не надо думать, что они все лицензии CC BY *свободны*. Дебиан так не считает, к примеру.
Ну и, хотя это там (и много где) действительно написано, не могу не отметить, что «совместимость в одну сторону» — это довольно странное с точки зрения языка выражение, порождающее нередко серьезные заблуждения. «Совместимость» — это возможность об’единять две работы (здесь — под двумя разными лицензиями) в рамках одной.
А по ссылке имеется в виду, что совместимость двух лицензий сильного авторского лева, обеспечивается явным ослаблением этого авторского лева только с одной стороны — со стороны «КК».
[0]
https://www.gnu.org/licenses/license-list.en.html#ccby 
Простой
Простой
