Нетрадиционные версии обобщенной вычислимости с оракулами тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

' л<? л

' ;Р .

■ а

российская академия наук а 1Б1 1рскок отделен! ш

институт математики им. сл.соболева

На правах рукописи УДК 517.11

ГЛНОВА Руслана Валерьевна

НЕТРАДИЦИОННЫЕ ПЕРСИИ ОБОБЩЕННОЙ ВЫЧИСЛИМОСТИ С ОРАКУЛАМИ

01.01.06 - математическая логика, алг ебра и теория чисел

Аптореферат дпееер пниш на соискание ученой степени кандидата фшмко-математических наук

НОВОСИБИРСК - 1998

Работ выполнена на кафедре алгебры и математической логигп Н'чюсибнрского государственного уштерситега.

Научный руководитель - доктор фнзпко-математнческих наук

Н.В.Белякнн.

Официальные ошюнепты - доктор физико-математических наук

Ы.М.Арена поп, кандидат физико-математических наук Л.Н.Победин.

Ведущая организация - Новосибирский Государственный

11едагогнческнй Университет.

/с 30

Защита состоится " 1ь " CuifiiMX' 199S г. н J-?_часов

ни заседании диссертационного совета Д 002.23.01 при Институте математики Сибирского отдел.ни" РАН по адресу: 630090, Новосибирск, 90, Унннерст¡гетскни проспект, 4.

С диссертацией можно ознакомится в библиотеке Института математики СО РАН.

Автореферат разослан " ^ " 1993,

Ученый секретарь .

диг-ертациопного с/.''Сч;

сопега Д 002.23.01 • ' '

к.ф.-м.н.

A.H.ÍWuh

ОБЩАЯ ПОСТАНОВКА ПРОБЛЕМЫ

Данная диссертация относится к разделу логики, называемому теорией абстрактной вычислимости, а конкретнее - к вычислениям с оракулами. Ьычисления с оракулами - это удобная форма изложения обобщенной вычислимости числовых (или преимущественно числовых) функций, так как другие объекты мож о закодировать такими функциями (например, ординалы можно представить в виде вычислимых деревьев) Машина с оракулом - это пара объектов один из

которых является конструктивным (машина Л/ и ее программа), а другой - теоретико-множесшенным (оракул !■). Такая машина работает согласно своей программе и может вычислять некоторые вопросы, представляемые числовыми кодами, которые передаются на выход оракулу Оракул - зто частичная числовая функция /<', присоединенная к специальному выходу машины во внешнюю среду. Ответом на прои- вольный вопрос V является значение оракула ¡'(у), это значение передается спрашивающей машине, и она продолжает работу. Однако, в работе машины с частичным оракулом /•' возможна особая ситуация, когда ¡нпчение ¡-'(у) не определено, т.е. машина получает отказ на вопрос у. И в >аких ситуациях мы можем принимать различные соглашения о поведении машины.

Во-первых, можно считать, что дальнейшая работа машины не определен) (в этом случае говорят, что машина с оракулам !•' зашг ла иа вопросе у) Именно такое естественное соглашение обычно принимается в современной теории вычислений на машинах с оракулом. Отметим, что при таком подходе все классические принципы программирования автоматически переносятся в эту теорию. Во-вторых, можно допустить, что в некоторых регламентированных ситуациях эш отказы машина воспринимает' как специфические ответы. Тогда возникает теория обобщенных вычислений, в которой, с одной стороны, могут нарушаться некоторые основные принципы теории алгоритмом . (например, такие как композиция программ, существование селекторной функции и г и ), а с другой стопины, обнаруживаются необычные и даже уникальные эффекты программирования. Исследовагие таких

нетрадиционных способов общения машины с оракулами и выявление соответствующих "программистских эффектов" состат'пяет главную цель длиной диссертации.

Пойнте оракула восходит eme к А.Тьюрингу, правда, первоначально отдавалось предпочтение питк :ьным ораку.ши. Оказалось, что принципы программирования па машинах с такими оракулами совпадают с принципами обычной теории алгоритмов, и потому зги вычисления не представляли особого интереса. Главное внимание здесь уделялось сравнению оракулов по их силе, и на основе этого возникла большая теория степеней неразрешимости. Вычисления с частичными оракулами вошли в математическую логику, начиная с основополагающих работ С.Клини [14]. и позволили сделать организацию вычислительных процессов более гибкой, даже при обычном, тьюринговом, понимании самою оракула, так как ни вы"ислсн|г.1 обладают определенными особенностями, обусловленными В01М0ЖН0етью неполучения ответа «vr оракула. Для машины г, работающей с одноместным частичным гракупом /•", существуют три варианта работы: z останавливается, - работает бесконечно, z застревает Наличие особого случая застревания не позволял механически переносить на вычисления с частичным оракулом некоторые стандартные конструкции из теории алгоритмов. Но несмотря на указанное ои.ичне вычислении с частичными одноместными оракулами oí рекурсивны, вычислений следующие аналоги простейших ciioiicii рекурсивных функции сохраняются, и более того, их доказательства совпадают с соответствующими рассуждениями теории алюртпмов.

1) Класс i -раз^чпнмы.ч множеств замкнут относительно операции объединения, пересечения, разности и декартова произведения.

2) Класс /-'-вычислимых функций замкнут относительно операции нолстаиоеки. _

J>) Существует /•'-вычислимая универсальная функции I '(:. х) такая, что выполняется соотношение (!{г, х) s {:¡> ( хК

4) Существует общерекурсивная функция Snm(z, х) такая, что для любого оракула /•' выполняется соотношение

,%">(:. х)>г( у) = х, у).

5) Д та произвольной /-вычислимой функции h(г, х) существует машина г такам, что выполняется соотношение

}е}! ( х) ¿ /){*-. х).

' ьче ,':,'■'( vi обозначает функцию от .г , вычислимую на машине с номером и оракулом символ ~ означает, что обе части равенства одновременно определены н принимают одинаковые значения

I c Tii при зтом варьировать еще и tuw ооиц-ния с njxiKv ioM, то

можно заранее ожидать появления каких-то дополнителып :х эффектов.

Главное отступление от традиционной версии оракульной вычислимости заключается в регламентированном допущении отказов (или ситуаций, приравниваемых к отказу). Например, можно считать, что машина может получать к отказов со стороны оракула и воспринимать их как специфические ответы, а при {кА /;-м отказе - "застревать". При исследовании этой версии всплывает еще одна возможная модификация, когда оракул реагирует не только на вопрос, но и на спрашивающую машину и, таким образом, является двуместной функцией. Причем, эта модификация может иметь и самостоятельный интерес. Впервые такого рода исследованиями занимался Л.Н.Победин.

Теория вычислений с частичными оракулами позволяет глубже ощутить принципиальную разницу между тотальными и частичными функциями. До возникновения теории алгоритмов все известные тогда алгоритмы фактически были тотальными, с точностью до тривиальных оговорок, т.е. применимы к любым входным данным. Естественно, что основными объектами рассмотрения этой теории являлись, вообще говоря, тотальные вычислимые функции. Частично рекурсивные функции были введены для получения удобного математического аппарата. Например, если рассматривать только общерекурсивные функции, то пришлось бы отказаться от универсальной функции. Таким обррзом, частично рекурсивные функции играли роль вспомогательных объектов, образующих своего рода "оболочку" для совокупности "настоящих" алгоритмов. Естественно возникает мысль о варьировании этой оболочки (при сохранении запаса тотальных вычислимых функций). 11 эта идея наиболее ярко реализуется на уровне вычислений с частичными оракулами. В работе [4] показывается, что можно построить два разных оракула, с которыми разрешимы одни и те же множества, однако >ги оракулы различаются на перечислимых объемах. Следовательно, не меняя "ядра", мы можем изменять "оболочку", получая дополнительные преимущества. Результаты данной диссертации тоже можно отнести к подобным исследованиям.

Заметим, что хотя речь идет именно об абстрактных вычислениях, г е. физически не реализуемых, тем не менее, с эвристической точки фения изучение оболочек можно представить как исследование основных принципов программирования, реализующихся в разнообразных вариантах обобщенной вычислимости. Естественно при этом возникают разные ситуации, в том числе, аналогичные тем, которые ворочаются и в компьютерной науке, например, в связи с я!ыками высокою уровня. Поэтому исследование нестандартных и лаже

уникальных эффектов "оракульного программировании" имеет

?

самостоятельный интерес, касающийся проблемы представления магемагичсских знаний. Данная диссертация как раз посвящена исследованию нетрадиционных способов общения с оракулами и выявлению соответствующих "программистских эффектов".

01>ЮР ДИССЕРТАЦИИ

Диссертация состоит из введения, трех глав, приложения и содержит 96 страниц.

Во введении определяются основные понятия, касающиеся чычислсний на машинах Тьюринга с оракулами, и рассматриваются некоторые основные особенности работы таких машин с тотальными и частичными оракулами. Вводятся определения регулярного и замкнутого относительно ч/амп-операцнн оракуле э. Формулируются основные свойства вычислений с такими ораку.лми. Далее, описываются нетрадиционные формы общения машины с оракулами и дается обзор известных и этом направлении результатов. В конце введения указаны основные публикации и доклады автора по теме диссертации.

В нерпой главе рассматриваются двуместщ г оракулы, близкие к тем, коюрымн ..анималеи в начале 70-\ годов Л.П Победим [6-8]. Эти оракулы представляют собой двуместный аналог итерированной клиниевекоц вычислимости, разрабопнпк.,1 в свое время Н.В.Белякнным, Е.Г.Иикифоровой н А.Н.Гамоаой [2-5, 9-11]. Победмн ставил перед собой следующую задачу: построить оракул, способный с одним допустимым отказом полуразрешать собственную проблему остановки. По ходу решения этой задачи были рассмотрены разные варианты, в частности, гнперарифметическая вычислимост ь была пронтерирована до первого конструктивно недостижимого ординала (что соответствует точке насыщения в итерированной клнннеискон вычислимости). Кроме того, Победии разработал некоторые приемы, используемые и в данной диссертации. Поэтому есть смысл остановиться на них чуть подробнее. Один из таких присмои - это то, что каждая машина размножена в бесконечном числе экземпляров, помеченных специальными индексами, кот орые бсрутс. из какой-нибудь ординальной нумерации к Мотивировка этого приема в следующем. Искомый оракул строится как предел трансфинитной последовательности расширяющихся оракулов ///:'. рассчитанных на то, чтобы отвечать на вопросы о поведении с ними различных машин при заданном числе до1 /стимых отказов. И

ь

здесь может возникнуть следующая неприятность: пусть машина : с оракулом Ну хорошо работает (не застревает), получая один отказ. При расширении оракула па этот вопрос может появиться ответ, и тогда : начнет работать уже по-другому. Следовательно, ответ оракула об 'пои машине тоже должен измениться. Победим предложил некое средство борьбы с л им явлением - "остановку времени". Представим последовательность трансфинитмых шагов построения оракула как моменты времени, и пусть в некоторый такой момент машина z не застревает, получая при этом отказы на какие-то свои вопросы. Тш да этой машине оракул не будет давать ответов и в более поздние моменты, даже если они у пего появятся. Кстати, именно отсюда и возникла идея двуместного оракула. По при этом обнаруживаются новые неудобства: вычислительные возможности, заложенные в некоторой программе, вследствие такого подхода могут оказаться нсшдсйствованными, потому что для машины "время может (становиться" раньше, чем она начнет работать задуманным образом. Чтобы обойти эту трудность как раз и вводятся индексы. Экземпляры одной и той же машины, по с разными индексами "вводятся в игру" (т.е. в процесс построения оракула-) на разных этапах. Так что замысел, заложенный в данной программе, реализуется хотя бы для тех ее экземпляров, которые были введены в игру достаточно "поздно", при более полном оракуле.

В данной диссертации сверх вышеописанных разработки новые приемы построения двуместных оракулов и к оракулу предъявляются соответствующие требования. Во-первых, оракул теперь должен содержать информацию о поведении машин с разным числом допустимых отказов. Считаем, что машина :j- работает н режиме j , если она может получить не больше j отказов, воспринимая и: как специфические ответы, а при у • /-м отказе ':zj ■ застревает. Во-вторых, ведется учет так называемых воплощений, т.е. рассматривается работа машины г относительно некоторой монотонной трансфинитной последовательности одноместных оракулов

H'n.H'i.....Н'у.... (I)

Ординал у называется моментом воплощения машины : относительно (I), если поведение z с оракулом Н\ сушестг -нно отличается от ее поведения с предыдущими оракулами. Доказывается, что для машины г, работающей в режиме у, число воплощений не превосходит о>1 • 1, где ш - первый бесконечный ординал (лемма 1.1). Для нумерации моментов воплощения фиксируется достаточно длин, ая ординальная нумерация / От оракула при этом требуем, чтобы он давал ir формацию о поведении машины в любом заданном члошении. Эга модификация нужна, в основном, для обеспечения большего схо; пва с итерированной

клиниевской вычислимостью, где существенную роль играет понятие точки насыщения. Поэтому и в данном варианте вычислимости желательно иметь подобные точки (и их удается определись подходящим образом). При этом замыкающий последовательность {//Y} оракул Н естественно раек, адывается в последовательность оракулов (Hóa), соответствующих "..арактериым" точкам процесса ею построения.

Основные результаты первой главы следующие. Во-первых, ее ли г - точка насыщения, то <)ля любой инициальной машины, хорошо работающей с HSz> существует а < т такое, что эта машина точно так же работает с H¿ja • Во-вторых, если рассмотреть итерированную клиниевскую вычислимость на той же нумерации, то се оракулы будут эквивалентны соответствующим орак;лам последовательности {И¿а].

Во второй главе рассматривается вычислимость с двуместными оракулами без допустимых отказов и без итерирования (а, значит, и без индексов), т.е. некий ослабленный вариант гиперарифметической вычислимости. В принципе, все упомянутые выше усовершенствования гоже межно ввести, но для того, чтобы отследить нужные нам эффекты в чистом виде, мы этого не делаем. Основной нал гнтерес состоит в следующем. Как известно, существую! алгоритмические проблемы, заведомо не разрешимые не только в обычной теории рекурсии, но даже с одноместными частичными оракулами (Оез допустимых отказов). Вот выразительный пример такой проблемы: каждое разрешимое множество является перечислимым, но приходится различать соответствующие коды, и задача состоит в том, чтобы по перечисляющему коду разрешимого множества найти его разрешающий код. Эта задача как раз и не разрешима в указанных выше ситуациях, и в §2.1 доказывается, что для любого одноместного оракула F не существует /'-вычислимой функции, которая по любому перечисляющему /'-коду множества А, разрешимого с оракулом F , давала бы разрешающий /'-код этого множества. Ситуация изменяется, если оракул является двухместной функцией: построенный во второй главе двуместный оракул решает эту задачу прямо по построению. Разумеется, полученное достижение не проходит даром, возникают проблемы в довольно неожиданной связи: простейшие приемы комбинирования вычислений (например, суперпозиция) не срабатывают в этой случае. Чтобы обойти ну труд' -.теть приходится слегка изменить само понятие вычислимости и вести так называемую "вычислимость в масштабе" Например, считаем,

что вычисление функции <р(п) производится на машине, работающей с аргументом 2п, т.е. основное вычисление как бы располагается на четных числах, а нечетные используются для принятия разных предупредительных мер (в связи с остановкой времени). Вместо множества четных чисел можно брать любые рекурсивные множества с бесконечными дополнениями, и в разных вычисмечиях их можно варьировать. За счет этого достигается замкнутость запаса вычислимых функций относительно суперпозиции и /.¡-оператора, но только для тотальных функций. Кроме того, в §2.3 доказывается, что построенный оракул Н является /7//-функцией.

В отличие от главы I, смысл задаваемых вопросов здесь немного меняете.,: теперь оракулы должны содержать информацию о поведении неиннциальных машин (без входных данных). Именно благодаря этому изменению и удается разрешить поставленную задачу, но за счет этого возникают и упомянутые выше трудности. Возможно, если рассмотреть не изолированный оракул /•", а его итерацию вдоль какой-нибудь ординальной чумерации, то недостатки оракула сгладятся. Для этого можно воспользоваться методами, описанными в [9].

В третьей главе рассматриваются вычисления с одноместными оракулами, но с допустимыми отказами. Здесь предпринимается "лобовая атака" на те трудности, которые в свое вгемя побудили Л Н.Победина перейти к двуместным оракулам. В ходе исследований существенно используется учет машинных воплощений Рассматриваемый оракул /•' задан уже в готовом виде, но на него накладываю юл определенные требования, которые предполапют, что /*' был построен неким трансфипитным процессом (в частности, мы гребуем, чтобы оракул Л'был разложим, т.е.

/•' и 1<у

У

и графики 1-у равномерно /'-разрешимы). Подходящим примером таких оракулов могут служить оракулы итерированной клинневской вычислимости в точках насыщения [9]. Ключевым понятием этой главы является понятие поисковой машины, возникающее т следующих рассуждений Берем произвольную инициальную машину г и среди вами обычной /-'-вычислимости порождаем последовательность моментов ее воплощений в режиме, скажем, одного допустимого отказа. Если ; имеет максимально возможное число воплощений (равное в данном случае <» Н), то подобное вычисление -'удег длиться бесконечно долго. В прошвном случае оно закончится, когда будет получен откн 1 при попытке найти очередное (в данном случае, последнее) воплощение

о

Машина, осуществляющая это вычисление, - поисковая машина - либо будет работа! ь с одним допустимым отказом и останавливаться; тогда по результат) ее работы можно выяснить все о поведении г с оракулом !•' ( по кис ется, в частности, застревающих машин). Либо, в случае когда г работает с /•' "совсем хорошо" (не получает отказов), поисковая машина может работать бесконечно, т.е. нерезультативно.

Описанная квазивычислимость дает повод расширить язык машин Тьюринга за счег введения новых команд - "комаид-декларации". В простейшем слуае они определяются следующим образом. Оракулу предьявляется некоторая машина г, и это понимается как запрос о поведении соответствующей поисковой машины !(:). Реакция оракула может представлять собой либо сообщение о том, что /(:) не получает отказов, либо оракул выдает первый отказной вопрос машины /(:). В первом случае реакция считается положительной, а во втором -отрицательной и приравнивается к отказу. Но теперь, если машина .т получит от оракула такой отказ и не застрянет, то тем самым л' получит и всю необходимую информацию о машине г. Поисковая машина (в силу своих особенностей) никогда не застревает, поэтому появляется шанс расстановить гибкость программирования с одноместным оракулом, утраченную за счет введения допустимых отказов.

Чтобы исследовать этот вопрос, в качестве модельной задачи мы берем парную селекцию. Основной результат состоит в том, что при определенных дополнительных требованиях к оракулу соответствующая вычислимость с декларациями оГааОаст аюиспншм пирпий селекции Кроме того, показано, что этот результат сохраняется при расширении языка программирования за счет новых команд (если соблюдаются подходящие дополнительные требования к языку). Это позволяет, например, преодолеть трудности при переходе от парной селекции к счсшой. связанные с накоплением отказов в процессе композиции программ.

В основном тексте диссертации преимущеивенно рассматривались проблемы оракульного программирования и не затрагивались возможности оракульного моделирования каких-либо математического теорий. Исследования такого рода предпринимались в работах [1, 5]. В приложении к данной диссертации показано как можно построить оракул, моделирующий некую нетрадиционную версию классической 1С0рни множеств, восходящую к Больцано и которую виоследствне разнил П.Вопеика [15]. Согласно этой версии универсум множеств предполагаемся неактуали)уемым, те сю всегда можно расширить и за сче! этого любое несчетное множество можно превратить в счетное. Лрушмн словами, множество несчсшо только в данный момент, ею

нельзя "сосчитать" лишь дозволенными средствами. При таком расширении универсума можно при помощи форсинга добиться, чтобч при этом выполнялась (или не выполнялась) какая-нибудь теорегико-множественпая гипотеза.

С каждым оракулом /"'можно связать некоторый запас вычислимых с ним абстрактных множеств (/'-множеств), в терминах которых (при подходящем выборе I) нетрудно построить универсум, моделирующий систему 7.П без аксиомы степени. Если тепер. дополнительно принять аксиому существования сильно недостижимого кардинала, то можно nocí роить такой /•', что в этом универсуме /--множеств будет существовать сколь угодно много моделей системы Z/\ Метод форсит а естественным образом вкладывается в Г-вычнслимосп., поэтому эти модели можно расширять, добиваясь упомянутых выше эффектов.

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

Основное содержание диссертации опубликовано в работах [17, 18. 19, 20. 21, 22]. Кроме того, полученные результаты неоднократно докладывались на различных научных студенческих конференциях ( MI1CK ), на семинарах "Алгебра и логика", "Конетрмчмивиые модели" (Новосибирский государственный университет), на семинаре по информатике в университете Г.Братислава (Comenius University in Bratislava, Faculty of Mathematics and Physics, 1996 г.). на Втором Сибирском Конгрессе по Прикладной Индустриальной маюмагпке (INPRIM-96, Новосибирск)

ЛИТЕРАТУРА

1. Ганов В.А. Обобщенная вычислимость и дескрпшивная теория множеств//Сиб.мат жури - 1971 -т.15, N6 - с. 1242-1261.

2. Ьелякин П.В. Итерированная клнниевская вычислимость и суперджамп/' Мат.сб., 1976. т. IОI, N1, с.21 -43.

3. Ьедякин Н.В

Итерированная клнниевская вычислимость' 11

Сиб.мат.журнал, 1989, т.ЗО, N6, с.26-41.

4. Бе 'якин Н.В Вычисления с оракулами// Труды ИМ СО АН СССР, 1989,т.12,с. 4 -24.

5. Белякин Н.В Пульсирующие иерархии// Сиб мат.журнал, 1994, т.35, N3.

6. Победин Л.Н. Некоторые вопросы обобщенной вычислимости // Алгебра и логика, 1973, т. 12, N2.

7. Победин Л.Н Проблема остановки и теория иерархий //Алгебра и логика, 1975, т. 14, N2.

8 Победин Л.Н. Вычислимость с двуместным оракулом // Сиб. мат. журнал, 1994, т.35, N5, с. 1138 - 1147.

9. Никифорова Е.Г. Некоторые модификации итерированной клиниевской вычислимости// Алгебра и логика, 1986, т.25, N3, с.292-314.

10. Никифорова Е.Г. Рекурсивные иерархии, регулярные по построению//Ред. ",Сиб. мат. ж\'рн.", - М., 1986. - Деп. В ВИНИТИ, N 5637 - В 86.

11. Никифорова Е.Г. Об одном способе регуляризащп, итерированной клиниевской вычислимости // Ред. "Сиб. мат. жури.", -М„ 1988. - Деп. в ВИНИТИ, N 2696 - В 88.

12. Роджерс X. Теория рекурсивных функций и эффективная вычислимость // М. : Мир, 1972.

13. Logic Cplloquium'69. Proceedings of the summer school and colloquium in mathematical logic//Amsterdam, London, 1971.

14 Kleene S C. Recursive fiinctionals and quantifiers of finite types // Trans. Amer. Math. Soc. 1959, v.91, p.1-52

15. Petr Vopenka. Uvod do matematiky v alternativnej teorii mnozin // "All';i", Bratislava, 1989.

16. Шенфилд Дж, Математическая логика // М.: Наука, 1975.

Рабоп.1 автора по теме диссертации

17 Гаиова I' В. Обобщенные вычисления с двумеешыми ораь> чами-' Алгебра и ло| нка, 1993, г 32, N5, с 479-196.

'8 Ganova R.V. On a Certain Nontraditional Version of Coinputations with <)iacles'/ Siberian Adv Math , I995,v 5. N2, p. 1.8- 4 7

19 Ганома P.В. Итерированная клиниевскач вычислимом ь с двумесшымн оракулами И Вычислшельные системы, Новосибирск, ИМ СОРА!!. 1997, вып. 158, с 53-62.

20 Гаиова Р В Оракульное моделирование теории множест// Ред "Сиб маг. жури" Сиб о гл. РАН, Новосибирск 1<)(>7 • Цен в ВИШПП, N 3296 -В г>7, 6 с.

21 Ганова РВ Heiралнпионные версии ораку.чыми смчистимосы. " Biopiiií (попрекни Хошресс по Прикладной и Индчсциы.ннин MaieMaiHKe (1IHIIPIIM-96), геч.докл - Новосибирск - Г/ 'Ъ • с 18<»

22. ¡anona РВ Орлкулысе программирование в чи-ч.-* высокого уровня ' Sihciian Adv Malh. 19'Ж (принято в печать).

i

i

, ч