Исправление SZT, (текущая версия) :
Во-первых сортировка может быть разрушающей и неразрушающей. У Вас какая?
У меня все чисто функционально, передаю в функцию массив по значению, сортированный массив потом мне возвращается из функции. А что там внутри делается - мне параллельно. Мне только важно, чтобы оно там мне вернуло в совокупности те же числа в том же количестве, что и поданные на вход, но при этом упорядоченные по возрастанию.
И во-вторых, а где ограничения на время работы, расход памяти?
Ну, можно предположить что у меня есть волшебная машина Тьюринга с бесконечной лентой, так что таких проблем у меня нет. А если серьезно отвечать, то такие ограничения вполне можно сформулировать на понятном человеку языке. Но тут уже надо привязываться к набору комманд конкретного процессора(вычислителя), чтобы однозначно определить лимит по памяти и числу «шагов». В качестве примера такого вычислителя, можно взять интерпретатор брейнфака с конечно-закицленной лентой, и определим зависимость размера массива от фактического количества инструкций, которые этот самый брейнфак может исполнить для сортировки массива, и длинной конечно-зацикленной ленты. Является ли логика первого порядка Тьюринг-полной? (комментарий) — скоро я надеюсь доделаю это описание брейнфака на языке STM-солвера, который эквивалентен логике первого порядка
Исходная версия SZT, :
Во-первых сортировка может быть разрушающей и неразрушающей. У Вас какая?
У меня все чисто функционально, передаю в функцию массив по значению, сортированный массив потом мне возвращается из функции. А что там внутри делается - мне параллельно. Мне только важно, чтобы оно там мне вернуло в совокупности те же числа в том же количестве, что и поданные на вход, но при этом упорядоченные по возрастанию.
И во-вторых, а где ограничения на время работы, расход памяти?
Ну, можно предположить что у меня есть волшебная машина Тьюринга с бесконечной лентой, так что таких проблем у меня нет. А если серьезно отвечать, то такие ограничения вполне можно сформулировать на понятном человеку языке. Но тут уже надо привязываться к набору комманд конкретного процессора(вычислителя), чтобы однозначно определить лимит по памяти и числу «шагов». В качестве примера такого вычислителя, можно взять интерпретатор брейнфака с конечно-закицленной лентой, и определим зависимость размера массива от фактического количества инструкций, которые этот самый брейнфак может исполнить для сортировки массива. Является ли логика первого порядка Тьюринг-полной? (комментарий) — скоро я надеюсь доделаю это описание брейнфака на языке STM-солвера, который эквивалентен логике первого порядка