При чём тут метатеория? Логический вывод должен опираться только на аксиоматику самой теории, но не метатеории. В метатеории своя метаарифметика.
Чтоб Вы знали - теоремы Гёделя о неполноте - это метатеоремы. Они рассматривают теории с точки зрения метатеории.
Прелесть Гёделевских номеров и предиката доказуемости в том, что они находятся внутри самой теории. Равно, как и правила вывода опираются только на формулы в самой теории. У метатеории свой язык, например.
Вы чего-то недопоняли. Ваш "предикат доказуемости" - это формула арифметики, но то, что эта формула выражает доказуемость в теории (содержащей арифметику), доказывается в метатеории.
Проблема в том, что ранее вы хотели это доказать при помощи правил вывода в рамках самой теории.
Нет, не хотели. Теорема Гёделя формулируется и доказывается не в рамках теории, о которой она говорит. Как такая абсурдная мысль вообще могла прийти в голову?
Мне зачем? Я не утверждаю, что это возможно. Сама идея выглядит нестрого.
Чтобы не офтопить. Если у Вас есть вопросы, которые уже очень далеко уходят от темы определения материи в школьном учебнике, то их нужно задавать не в этой теме. Давайте уважать интересы топикстартера.
Только теорию множеств построили до теории алгоритмов.
Это спорный вопрос. ZFC окончательно сложилась году эдак в 1925-ом. Понятие о рекурсивных функциях ввел, вроде как, Дедекинд году в 1888-ом, хотя машины Поста и Тьюринга придумали в 1936-ом.
Кроме того, с алгоритмами есть много подводных камней, не менее сложных, чем парадоксы теории множеств. Например, та же проблема остановки.
И что? Проблема останова - это просто задача, которая не решается на нижнем уровне аналитической иерархии. Теория множеств смело заявляет, что у этой проблемы есть решение (хотя на самом деле никто его не видел), вводя следующий уровень аналитической иерархии. Тем не менее, это не спасает от того, что на этом уровне тоже есть неразрешимые задачи, которые "решаются" на следующем и т.д.
Или если он недетерминированный вдруг. Или если у компьютера, для которого вы написали ваш "алгоритм", переполнится память.
По-моему, Вы сейчас вообще что-то не по делу говорите.
Вы же не хотите рассматривать в качестве примера "довольно простой вещи" машины Тьюринга, надеюсь?
Я же сказал: всего лишь код (на любом языке программирования) и правила его выполнения. Машина Тьюринга или иная машина - не суть важно. Это несоизмеримо проще, чем какие-нибудь большие кардинальности в теории множеств.