Сервис онлайн-записи на собственном Telegram-боте

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
Для новых пользователей первый месяц бесплатно.

Чат-бот для мастеров и специалистов, который упрощает ведение записей:

— Сам записывает клиентов и напоминает им о визите;
— Персонализирует скидки, чаевые, кэшбэк и предоплаты;
— Увеличивает доходимость и помогает больше зарабатывать;

Начать пользоваться сервисом

Как продвинуть сайт на первые места?

Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.

Ускорение продвижения

Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.

Начать продвижение сайта

Теорема 7. 2

Числовая функция f (x, y) = xy не вычисляется конечными автоматами.

Доказательство

Предположим противное. Пусть существует конечный автомат Á = (A, B, Q, j, y), который из начального состояния q ₀ вычисляет f.

Здесь A = { 00, 01, 10, 11 }, B = { 0, 1 } и Q = { q ₁,..., q_k }.

Пусть перемножаются два числа, большее из которых представляется в двоичной системе записью длины d. Тогда длина произведения двух таких чисел может достигать длины 2d-1. При этом, если представлять такие произведения двоичными записями длины 2d-1, то первые d компонент в них могут быть любыми двоичными последовательностями длины d.

Будем считать, что перемножаемые числа x и y, большее из которых представляется двоичной записью длины d, пополняются незначащими нулями и записываются в виде наборов длины 2d-1.

Перемножаемые числа поступают на вход Á в виде последовательности пар значений одноименных двоичных разрядов, начиная с младших разрядов.

Пусть - входное слово автомата Á, представляющее два перемножаемых числа x и y. Автомат заканчивает переработку первых d символов в некотором состоянии q _i.

После этого на вход Á поступают остальные символы в виде последовательности d-1 пар нулей.

Значения появляющихся при этом символов на выходе автомата образуют слово длины d-1, определяемое только состоянием q _i.

Поэтому значения первых d разрядов произведений произвольных чисел длины d могут принимать не более k различных значений.

Поэтому для любого значения d должно выполняться неравенство: k ³ 2^d-1.

Поскольку значение k является фиксированным, а d - произвольное, то последнее неравенство неверно.

Следовательно, предположение о существовании автомата Á, вычисляющего функцию умножения пар чисел, неверно.

Доказательство окончено.

Упражнение.

1. Доказать, что для любого фиксированного натурального числа n существует конечный автомат, вычисляющий функцию f (x) = n ´ x;

2. Доказать, что не существует конечного автомата, вычисляющего функцию f (x, y) = div(x, y).

Имеет место еще одно свойство, ограничивающее вычислительные возможности автоматов, следующее из конечности множеств состояний.

Пусть A = { a ₁,..., a _n } - некоторый алфавит. Всякая бесконечная последовательность символов этого алфавита называется сверхсловом в A. Множество всех сверхслов в алфавите A обозначается как .

Сверхслово называется периодическим, если оно может быть представлено в виде: = ()^¥ . Здесь и - слова в алфавите A. Сверхслово ()^¥ получается сцеплением слова и сверхслова ()^¥ , получаемого последовательным выписыванием бесконечное число раз. Слово называется периодом, а ()^¥ - периодической частью сверхслова .

Если автомат Á в момент t ₀находится в начальном состоянии q₀ и в моменты времени t₀, t₀ + 1,... на его вход поступают символы сверхслова , то в эти же моменты времени на выходе Á появляются символы выходного алфавита, образующие выходное сверхслово .

В этом случае будем говорить, что Á из начального состояния q₀ перерабатывает входное сверхслово в выходное сверхслово .