1) N конечно же гораздо больше, чем башня из миллиарда двоек, где-то на FOM написаны нижние оценки.
Важно не то какое N по величине, а что оно означает и как оно отвечает за структуру (в смысле вложения друг в дружку) конечных деревьев не очень большого размера.

2) нет, аргументы с "конечной вселенной" не имеют отношения к философии финитизма.

3) да, представлят себе деревянные палочки (спички) и "абстрагируется", но не слишком сильно: всегда нужно не сомневаться, что то, что мы делаем с палочками можно сесть и сделать.

4) конструктивисты докомпьютерной эры (1950х-1960х годов) не интересовались вопросами сложности вычислений, поэтому сейчас их дискурс с легкостью критикуют информатики, на основании современных представлений бытующих в головах computer scientistов.

(Reply to this) (Parent) (Thread)

>N конечно же гораздо больше, чем башня из миллиарда двоек,
Вот теперь я знаю, что имеют ввиду логики, когда говорят, что число не очень большое :-)

>да, представлят себе деревянные палочки (спички) и "абстрагируется", но не слишком сильно: всегда нужно не сомневаться, что то, что мы делаем с палочками можно сесть и сделать.

Вы всё опять запутали. Как понимать слова сесть и сделать?
Конкретный пример: http://en.wikipedia.org/wiki/Graham_number
Вот я сейчас сяду и напишу программу для машины Тьюринга,
которая всё в лоб перебирает, пока не найдёт правильный ответ.
Теоретически она может работать вплоть до, скажем,
примерно половины этого числа Грехема.
Такое число мы не сможем записать никогда.
Допустима ли такая программа с точки зрения конструктивизма?
Если да, то как следует понимать ваши слова про сесть и сделать?

>конструктивисты докомпьютерной эры (1950х-1960х годов) не интересовались вопросами сложности вычислений, поэтому сейчас их дискурс с легкостью критикуют информатики, на основании современных представлений бытующих в головах computer scientistов.

Это конечно. Собственно, моя критика является очень слабой
версией этой критики.

(Reply to this) (Parent) (Thread)

про число Грэма в википедии написана неправда и профанация: это достаточно маленькое число, не входящее даже в первую двадцадку известных коротко определенных больших чисел. В первых строчках стоят разные числа из Ратьеновского Пи-1-2 анализа, следующим эшелоном идут числа из теоремы о минорах графов, третьим эшелоном - разные числа из теорем о частичных вполне-упорядочениях (например в низких слоях третьэго эшелона лежит Крускалово число(5), определение которого я выписал. Четвертый эшелон - разные рамсеевы числа. Где-то в самом низу четвертого эшелона маячит Грэмово число...

(Reply to this) (Parent) (Thread)

Очень интересно. Впрочем, это не отменяет моего вопроса
про конструктивность вычисления с числом операций порядка числа Грехема.

Было бы очень интересно узнать про эти эшелоны чуть подробнее.
Что это за Пи-1-2 анализ такой, например?
Возможно, имеет смысл написать отдельный (не очень большой) пост про это?

А вот, скажем, если обозначить за t(n) максимальное количество
операций, которое может выполнить машина Тьюринга с n состояниями,
то в каком эшелоне будут сидеть числа t(n)?

(Reply to this) (Parent) (Thread)

про эшелоны это я так выразился, для поэтичности: каждому "эшелону" соответствует формальная теория в которой известно простое недоказуемое Пи_2 утверждение.

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

Про разные теории можно почитать в книжке S.Simpson "Subsystems of second-order arithmetic".

Про недоказуемость - в моей недавней писульке здесь: article

Про t(n) (и про соответствующие большие числа из диофантовыx игр) я пока серьезно не думал, хотя кое-какие банальности про доказуемо-рекурсивные функции сказать мог бы.

(Reply to this) (Parent)