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

Дружок, ну зачем ты повторяешь раз за разом выдуманную ересь? Возьми и открой учебник, там же все написано.

Есть теорема, которая устанавливает эквивалентность между частично-рекурсивными ф-ми, МТ и лямбдами (это теорема). И дальше в качестве определения вычислимой ф-и принимается ф-я, представимая одним из этих эквивалентных способов (это как раз тезис Черча-Тьюринга).

Ты думаешь что мы поведемся на такой простой демагогический прием? Что за дичь ты нам пытаешься впарить? Сама программа (запись на языке программирования) ни про какой стек и его размер ничего не знает. Выпадение StackOverflowException никак не следует из записи программы. Соответственно, превращение такого кода в код вызывающий SOE - изменяет семантику, т.е. это неэквивалентное, неправильное преобразование. Дай пожалуйста нормальное преобразование, которое не падает со всякими из воздуха берущимися ниоткуда не следуюищми экзепшенами и мы тебе сразу поверим!

Да. Это то, что следует понимать под итерационной формой, чтобы содержательно ответить на вопрос ОПа. Если ты обсуждать вопрос ОПа не хочешь, а зашел сюда просто повыебываться - то проходи мимо.

Ну или можешь предложить свои варианты определения рекурсивного/итерационного процесса.

Дай пожалуйста нормальное преобразование, которое не падает со всякими из воздуха берущимися ниоткуда не следуюищми экзепшенами и мы тебе сразу поверим!

Без гото произвольная рекурсия к циклу не приведется. Если разрешить гото - то CPS трансформация и замена хвостовых вызовов джампами, в результате падать у тебя ничего не будет, так как стек будет храниться в хипе.

таблетки принять забыл?

тезис — он на то и тезис, что его ни доказать, ни опровергнуть не выходит. это раз. разберись что именно он утверждает, и не из википедии, а из нормального источника. это два.

русская терминология в области мат логики весьма убога, да. но это не повод для анонимуса нести всякую чушь основываясь на своих интуитивных представлениях.

Дай пожалуйста нормальное преобразование, которое не падает со всякими из воздуха берущимися ниоткуда не следуюищми экзепшенами и мы тебе сразу поверим!

зависание подойдёт?

тезис — он на то и тезис, что его ни доказать, ни опровергнуть не выходит.

А где я говорил, что его можно доказать? Еще раз - эквивалентность частично-рекурсивных ф-й, лямбд и МТ - это не тезис Черча-Тьюринга. Это просто теорема. Она доказана, да, четко и строго. Эта теорема стала причиной того, что тезис был сформулирован. Сам тезис заключается в том, что неформальное понятие «вычислимой функции» было предложено определять как «ф-я, представимая в одной из вышеперечисленных эквивалентных форм».

русская терминология в области мат логики весьма убога, да.

При чем тут русская терминология, дебилушка?

Вот тебе цитаты, с-но, авторов тезиса: [qoute] THESIS I. Every effectively calculable function (effectively decidable predicate) is general[28] recursive [Kleene's italics] «Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it ... так и написано - „возьмем в качестве определения эффективное вычислимой функции понятие частично-рекурсивной ф-и“ (что эквивалентно лямбдам и МТ, как было доказано перед этим, что и послуэило причиной формулирования тезиса).

А где я говорил, что его можно доказать?

Это просто теорема.

прохладная история. тогда с тебя точная формулировка тезиса :) хинт: вычислимые по тьюрингу функции являются интуитивным понятием, и поэтому не могут фигурировать в качестве субъекта доказательства.

При чем тут русская терминология, дебилушка?

Every effectively calculable function (effectively decidable predicate) is general[28] recursive

слово «general» твой межушный ганглий способен перевести?

update

так и написано - „возьмем в качестве определения эффективное вычислимой функции понятие частично-рекурсивной ф-и“

понял. неспособен. соболезную.

тогда с тебя точная формулировка тезиса

Я для кого выше цитату дал?

«This heuristic fact [general recursive functions are effectively calculable] ... led Church to state the following thesis(22). The same thesis is implicit in Turing's description of computing machines(23). „THESIS I. Every effectively calculable function (effectively decidable predicate) is general[28] recursive [Kleene's italics] „Since a precise mathematical definition of the term effectively calculable (effectively decidable) has been wanting, we can take this thesis ... as a definition of it ...“[29] “(22) references Church 1936 »(23) references Turing 1936–7

слово «general» твой межушный ганглий способен перевести?

Слово general относится не к тотальности ф-й, а к типу рекурсии (general recursion, рекурсия общего вида, в отличии от примитивной рекурсии), то есть general recursive functions - это частично-рекурсивные функции. А общерекурсивные (тотальные, то бишь) ф-и так и называются total recursive functions. А ты - долбоеб.

Кстати, теб даже на русской википедии специально про это указали:

Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических причин и по сути являются результатом неточного перевода английских терминов partial recursive function и total recursive function

Но ты же дебил, дочитать до конца не способен.

general recursive functions - это частично-рекурсивные функции

... а куликовская битва была совсем недавно в пригородах москвы...

с альтернативной наукой в другое место, пожалуйста.

Ебанько, открой уже учебник и прочитай, какие функции называются general recursive, а какие - total recursive.

Вот тебе чтобы не искал: http://people.ucalgary.ca/~rzach/static/open-logic/computability/recursive-fu...

и вот: http://math.stackexchange.com/questions/75296/what-is-the-difference-between-...

и еще: http://www.cs.cmu.edu/~cdm/pdf/PrimRec-6up.pdf

аналога «general recursive» (это термин из метаматематики гёделя) афаик в русском вообще нет. сейчас используются общерекурсивные (total recursive) и частично-рекурсивные (partial recursive).

http://math.stackexchange.com/questions

тоже прохладно.

открой клини, наконец. его на русский ещё при ссср переводили.

аналога «general recursive» (это термин из метаматематики гёделя) афаик в русском вообще нет.

Ебанько, general recursive = partial recursive. 57-58 слайд в третьей пдфке, ебанько. Или почитай того же Клини, у него это все тоже написано.

занятно. т.е. ты не читаешь перед тем как постить?

Вот тебе чтобы не искал: http://people.ucalgary.ca/~rzach/static/open-logic/computability/recursive-fu...

Clearly every general recursive function is total.

рекурсивная => нерекурсивная реализация (комментарий)

:)

алсо

So the word \general," a historic relic, is a misnomer; on the surface

первая ссылка просто фееричной оказалась. умеют же учить буржуи...

любая рекурсия может быть привращена в итеративную запись, правильно?

Это как теорема существования и единственности в математике, т.е. для практики толку немного. И кстати не любая, если еще окончательно не забыл математику. Бесконечная рекурсия не может быть превращена, но ее и не реализовать на компьютере. Чем-то сродни пределу.

Поздравляю, нашелся еще один дебил вроде тебя. Две другие ссылки ты не смотрел, я правильно понял?

А вообще: http://mathworld.wolfram.com/GeneralRecursiveFunction.html

Так что надо смотреть на конкретные определения. У Черча и Тьюринга general = partial.

авторитет stackexchange для меня не превышает местный; третья ссылка напугала слайдами — я плохо воспринимаю информацию, отформатированную для умственно-отсталых.

теперь рассказывай в каком опиумном притоне «general» переводят как «частичный».

я тебе выше объяснял, что между «general recursive function» гёделя (кстати, именно с твоего кукареканья поэтому поводу и началась наша беседа) и «total recursive function» чёрча прошло слишком мало времени (интернетов тогда не было, да) и они приехали в ссср одновременно и получили один перевод на двоих.

У Черча и Тьюринга general = partial.

обоснуй

теперь рассказывай в каком опиумном притоне «general» переводят как «частичный».

Его не переводят как частный, при чем тут вообще перевод? Речь о том, что general и partial используются как синонимы. А когда речь идет о тотальности, то так и говорят - total.

кстати, именно с твоего кукареканья поэтому поводу и началась наша беседа

Напомню, что это ты начал кукарекать про мифическую, одному тебе известную «теорию Геделя».

и они приехали в ссср одновременно и получили один перевод на двоих.

Да при чем тут, когда они приехали в СССР? При чем тут вообще перевод?

Речь о том, что general и partial используются как синонимы.

это какой-то неологизм. ни чёрч, ни тьюринг о нём, к сожалению, ничего не знали. насколько я понял по вольфраму (на соседней странице про «рекурсивные функции» без предваряющих прилагательных взаимоисключающие параграфы детектед... так что отношение к ресурсу соответствующее), существует секта, которая утверждает что general = total + partial, и ты являешься её адептом (хотя из твоих слов вытекает более дикое и нелогичное утверждение).

Напомню, что это ты начал кукарекать про мифическую, одному тебе известную «теорию Геделя».

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

Да при чем тут, когда они приехали в СССР? При чем тут вообще перевод?

при том что мы общаемся на русском?

Потому что если интерпретировать как total, то тезис становится полностью бессмысленным, как и понятие вычислимости.

Это бы имело смысл, если бы мы для любой частично-рекурсивной ф-и могли написать тотальную, которая бы нам на области определения частично-рекурсивной возвращала то же самое, а вне ее, какой-нибудь специальный маркер (ну например 0). Но это нельзя (т.к. проблема останова неразрешима и мы не можем никак узнать, что «щас я хочу вернуть 0» - для этого надо определить, что программа виснет).

То есть получается такая ситуация - возьмем некое подмножество натуральных чисел и рассмотрим на нем тотальные ф-и, так вот, если считать что это все вычислимые ф-и на данном множестве, то получается нонсенс - так как существуют ф-и на целом множестве натуральных, которые на нашем подмножестве определены лишь _частично_, но при этом не совпадают ни с одной тотальной ф-ей, то есть мы можем вычислить ф-ю, которая объявлена невычислимой.

Или, иначе - у нас может быть некоторое подмножество МТ и их начальных данных таких, что не существует тотальной ф-и на этом подмножестве, которая на нем решает задачу разрешимости, но при этом может вполне существовать нетотальная ф-я на всем множестве МТ+данные, которая в точности на всех МТ+данные подмножества проблему останова решает, а на остальных МТ+данные - виснет.

И, значит, расширив множества МТ+данных неким надмножеством, мы можем задать нетотальную ф-ю на этом надмножестве, которая будет в точности решать полностью задачу останова для всех МТ+данные (точнее не то, что можем, но «неразрешимость» не запрещает нам так делать, вот в чем суть). Отлично, чо. Какой смысл в такой неразрешимости тогда?

существует секта, которая утверждает что general = total + partial

Все с точностью до наоборот. Это у вас секта.

при том что мы общаемся на русском?

если говорить о русском, то тут все понятно - вычислимые = частично-рекурсивные, частично-рекурсивные = вычислимые > общерекурсивные.

Вопрос исключительно об английском - что значит general.

которые на нашем подмножестве определены лишь _частично_

На множестве - частично, а на подмножестве - полностью, конечно, selffix.

разработал теорию рекурсивных функций.

Только вот никто ее теорией Геделя не называет. Наверное, потому что он много чего разработал.

Ой, у языков типа java уже появилась не зависящая от реализации семантика? Ну, круто, чо.

http://docs.oracle.com/javase/specs/jls/se8/html/index.html не?

вот и я говорю: путаница с терминологией просто грандиозна.

чёрч сформулировал свой тезис как эквивалентность общерекурсивных функций интуитивно вычислимым. тьюринг сопоставил им же вычислимые на своей машине функции. позже тот же фокус проделали пост и дойч.

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

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

чёрч сформулировал свой тезис как эквивалентность общерекурсивных функций интуитивно вычислимым.

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

В таком определении «вычислимости» получается, например, что невычислимость проблемы останова не говорит о том, что нету алгоритма, который бы мог решить проблему останова. Это же чепуха. Зачем такая «вычислимость» вообще нужна тогда?

по-моему автор спрашивал как ему автоматически переписать код чтобы избежать ограничений на размер машинного стека, а вы тут развели.

так ведь специальный софт типа Maple может символьно брать пределы? :)

Так и полноценный TCО для хвостовой рекурсии можно в любом языке реализовать через «трамплин», даже в Scala, но только так почти не делают :)

Кстати, в Scala действительно хотели, даже в статьях упоминали об этом, но потом передумали, видимо, когда осознали последствия.

но потом передумали, видимо, когда осознали последствия.

Какие?

Так на это ему ответили давно, про CPS и вывод минимально необходимого искусственного стека (или дерева в некоторых случаях).

Была бы очень медленная реализация, видимо.

Если бы ты хоть немного писал на ассемблере, ты бы знал, что все эти команды — call, ret, loop — вполне могут быть использованы и для совершенно других целей

конечно можно. В сишке тоже можно число типа int хранить и обрабатывать как строку в десятичной СС. Много чего «можно», например хрен сломать с дуру.

Классический пример

я знаю, что в асме полно грязных хаков вроде этого.

Вот только у меня не какой-то helloworld школьника на асме, а продукт сгенерированный gcc. Там CALL означает «вызов функции». В данном случае рекурсивный.

Только потому, что обычно люди не напрягаются с переписыванием в нерекурсивную форму, если это ничего не даёт. Но в вопросе данное требование не ставилось.

gcc напрягается, если в этом есть профит.

А в вопросе ТС исходил из неправильной предпосылки, что якобы «рекурсия это плохо». На самом деле это не хорошо и не плохо, если костыльный стек засрёт Over9000Mb, а потом рухнет, это ничем не лучше железного варианта. Только дольше.

что же мешает ф-ции, определенной на всем множестве быть переписанной в итеративный вид?

дык перепиши обход бинарного дерева, что тебе мешает?

Да, компиляторы не существуют.

да, не существуют компиляторы, порождающие код, который не сегфолтится от нехватки стека.

Т.е. компиляторы существуют, вот только они не работают как в твоих влажных фантазиях.

функция которая использует стек (в любом виде) - рекурсивная.

нет.

int f(int x)
{
  return x*x;
}

int main()
{
  return f(7);
}

fact n = n*fact(n-1) //рекурсивный процесс, можно переписать в CPS завелосипедить свой стек и т.п. - эти трансформации можно сделать автоматически и убирают явную рекурсию, но процесс остается рекурсивным

детка, учи матчасть. GCC эту функцию делает итеративной, без всяких стеков, циклом. Фишка в том, что значение n в стековом фрейме не используется, а значит можно хранить n в одном и том же регистре всю дорогу.

А вот в функции Аккермана такой вариант уже не сработает.

Бесконечная рекурсия не может быть превращена, но ее и не реализовать на компьютере.

man бинарное дерево. Никто не обещал, что это дерево будет конечным. Потому, тебе явно или не явно придётся в коде ограничить глубину дерева. На практике, если дерево сбалансировано, то нужно O(log(N)), чего достаточно для любых практических целей.

fact n = n*fact(n-1) //рекурсивный процесс, можно переписать в CPS завелосипедить свой стек и т.п. - эти трансформации можно сделать автоматически и убирают явную рекурсию, но процесс остается рекурсивным

детка, учи матчасть. GCC эту функцию делает итеративной, без всяких стеков, циклом. Фишка в том, что значение n в стековом фрейме не используется, а значит можно хранить n в одном и том же регистре всю дорогу.

#include <stdio.h>

int fact(int N) {
        if (N < 1) return 1;
        else return N * fact(N - 1);
}

int main () {
        return fact(10);
}

_Z4facti:
.LFB0:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6                                                                                                                                                           
        subq    $16, %rsp                                                                                                                                                                 
        movl    %edi, -4(%rbp)                                                                                                                                                            
        cmpl    $0, -4(%rbp)                                                                                                                                                              
        jg      .L2                                                                                                                                                                       
        movl    $1, %eax                                                                                                                                                                  
        jmp     .L3                                                                                                                                                                       
.L2:                                                                                                                                                                                      
        movl    -4(%rbp), %eax                                                                                                                                                            
        subl    $1, %eax                                                                                                                                                                  
        movl    %eax, %edi                                                                                                                                                                
        call    _Z4facti                                                                                                                                                                  
        imull   -4(%rbp), %eax                                                                                                                                                            
.L3:                                                                                                                                                                                      
        leave
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE0:
        .size   _Z4facti, .-_Z4facti
        .globl  main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    $10, %edi
        call    _Z4facti
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc

оптимизацию включи.

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

А оптимизация как бы не всегда возможна:

#include <stdio.h>

int fact(volatile int N) {
        if (N < 1) return 1;
        else return N * fact(N - 1);
}

int main () {
        return fact(1000);
}

$gcc -S -O2 main.c

.LHOTB0:
        .p2align 4,,15
        .globl  _Z4facti
        .type   _Z4facti, @function
_Z4facti:
.LFB30:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movl    $1, %eax
        movl    %edi, 12(%rsp)
        movl    12(%rsp), %edx
        testl   %edx, %edx
        jle     .L2
        movl    12(%rsp), %edi
        subl    $1, %edi
        call    _Z4facti
        movl    12(%rsp), %edx
        imull   %edx, %eax
.L2:
        addq    $24, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE30:
        .size   _Z4facti, .-_Z4facti
        .section        .text.unlikely
.LCOLDE0:
        .text
.LHOTE0:
        .section        .text.unlikely
.LCOLDB1:
        .section        .text.startup,"ax",@progbits
.LHOTB1:
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB31:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $999, %edi
        call    _Z4facti
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        imull   $1000, %eax, %eax
        ret
        .cfi_endproc
.LFE31:
        .size   main, .-main
        .section        .text.unlikely
.LCOLDE1:
        .section        .text.startup

На чем-нибудь сложнее расчета факториала можно и в ногу выстрелить слишком уж полагаясь на компилятор.