Сильная индукция: кончится ли опись

Тимофей Ильич · архивариус

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

Костя задал правильный вопрос. Правило Тимофея Ильича ссылается само на себя: «опиши коробку» внутри говорит «опиши коробку». Такое правило называют рекурсивным. Программисты пишут такие правила каждый день и каждый раз рискуют: правило может ссылаться на себя без конца, и программа зависнет.

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