Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

о кванторах (математическое)

I hate the Pumping Lemma (англ.)

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

В обсуждении на Hacker News кто-то справедливо заметил, что лемму о накачке следует объяснять, начиная с доказательства, потому что оно практически тривиально и очень интуитивно. Правда, даже если доказательство понятно, многим трудно переварить что-то вроде "∀ регулярного языка L ∃ n > 0, так что ∀ слова длиной больше n ∃ такая его разбивка, что.... (и еще внутри этого: ∀ степени i...)".

Но может быть, подумал я, это как раз является одной из причин, по которым лемма о накачке неизбежно оказывается частью обучения степени Computer Science? Для студента CS она оказывается обычно первым "заумным" с точки зрения логики утверждением, таким, которое требует нормального понимания чередующихся кванторов. А это понимание надо наработать в себе тем или иным образом, надо сквозь него пройти. Более сложный материал в более сложных курсах потом всегда будет принимать это понимание как данное.

Людям, вообще говоря, трудно даются цепочки чередующихся кванторов: утверждения типа "для каждого X сущестует такое Y, что для каждого Z..." Никто не понимает такие утверждения, встретив их впервые, сразу и интуитивно: надо сломать на них мозги, надо как следует продумать их. Даже цепочка длиной 2 уже трудна для неподготовленного человека; студенты-первокурсники часто путают ∀∃ с ∃∀. Многие, пройдя сквозь этот процесс тренировки, забывают о нем потом; цепочки длиной 2-3 кажутся им тривиальными и немедленно доступными любому.

Как раз недавно мне попался типичный пример - на том же форуме HN обсуждали запись в блоге программиста-самоучки (без высшего образования), о том, как понять нотацию O() без математики. Запись, по-моему, была не очень удачная, но меня поразил один комментарий: "да вообще-то это просто. Скажем, время работы O(n) означает, что есть такая константа..." и дальше словами выписано, что такое для функции быть O(n), и заканчивается так: "видите, хоть и математика, но очень просто!". Причем это было написано совершенно без иронии, автор комментария был искренне уверен, что выписанное словами утверждение с чередующимися кванторами будет совершенно прозрачным для любого программиста-самоучки без высшего образования.

Похожий процесс тренировки работы с кванторами происходит, мне кажется, у студентов-математиков (и других) во время первого строгого курса анализа, когда они встречаются с доказательствами с эпсилонами-дельтами. В западных университетах, если я правильно понимаю, "настоящие" математические предметы обычно начинаются со строгого матанализа, и часто одновременно линейной алгебры, а абстрактная алгебра остается на потом. При этом, вообще говоря, необязательно это устраивать именно так: почему бы не начать с линейной алгебры и абстрактной алгебры, скажем, тем более, что студенты обычно уже учили анализ в нестрогом виде, как "calculus", в последних классах школы или в начальных курсах колледжа? Почему не отложить строгий матанализ на после абстрактной алгебры и общей топологии? Может быть, как раз потому, что эпсилоны-дельты, как ни ненавидят их многие студенты, натаскивают их и доводят до того уровня автоматизма в понимании чередующихся кванторов, без которого им намного тяжелее давались бы эти другие предметы. Возможно, они, эпсилоны-дельты, играют таким образом более важную педагогическую роль, чем собственно строгое объяснение понятий пределов, непрерывности и производной.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 53 comments