Вообще говоря, чтобы предметно спорить по теории программирования, нам следует ссылаться на литературу по теории программирования.
Я к сожалению, компьютер сайенс курса не слышал, поэтому я такой литературы не знаю.
Мои сведения о чистых функциях я почерпнул из учебной литературы по языку Haskell.
И я не знаю, как у вас в Википедии, но у нас в Хаскеле действуют следующие определения:

Детерминированностью функции называется однозначное состояние выхода зависящее только от состояния входа и не зависящее от каких бы то ни было внешних состояний.

Побочным эффектом функции называется возможность функции подействовать на какое либо внешнее состояние (переменную, физическую реальность посредством вывода).

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

В английской версии написано "при побочных эффектах результат работы функции может зависеть от истории". Может зависеть, а может независеть... Я нахожу данное определение бессодержательным.

Пример недетерминированной функции - функция чтения из файла. Одному и тому-же имени файла может соответствовать совершенно разное содержимое. Причем как сиюминутно, так и в течении времени. Никто не гарантирует определенную историю изменения файла.

Пример функции с побочным эффектом - функция записи в файл.