Геделевская нумерация - как это сделать самому?

[valambar]

Геделевскую нумерацию я встречал не только в методе доказательства теоремы Геделя (к счастью, попалась книжка, которая объясняет это доказательство довольно просто), но и в пособии по теории автоматов. Из чего понял, что это - довольно распространенный метод решения многих задач в разных разделах математики. На первый взгляд этот метод не выглядит очень сложным. Поэтому у меня следующие вопросы:

1. Какие типы задач решаются этим методом?

2. Как эту нумерацию ввести самому, ну допустим, я хочу "изобрести велосипед" и поставить в соответствие логические и арифметические операции (то есть повторить путь Геделя)?

[arseniiv]

Ну вот вы видели пример её введения — что осталось непонятным? Неясно, в чём могут возникнуть трудности. Можно даже нумеровать двумя способами: в соответствии с индуктивным определением множества формул и в соответствии с тем, какими строками они кодируются. Можно вообще сразу понимать строковую запись как гёделевскую нумерацию в (мощность алфавита + 1)-ичной системе счисления, где каждому символу соответствует ненулевая цифра, а строке — число, записанное в этой системе. С другой стороны, можно задать даже биективное соответствие между всеми строками над интересующим алфавитом и натуральными числами — тут вместо обычной позиционной берётся т. н. биективная система счисления. Первый же способ, в принципе, тоже сводится ко второму (польская запись).