Лингвофорум

Цитата: Agnius от февраля  9, 2022, 16:47
Можно еще вспомнить Успенского - доказательство то, что убеждает.

Цитата: 6. Что такое доказательство?Итак, термин «доказательство» — один из самых главных в математике — не имеет точного определения. А приблизительное его определение таково: доказательство — это убедительное рассуждение, убеждающее нас настолько, что с его помощью мы способны убеждать других [12].

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

Цитата: Agnius от февраля  9, 2022, 16:47
Можно еще вспомнить Успенского - доказательство то, что убеждает. А значит если нам что-то достаточно очевидно для того, чтобы это нас убедило, то это и доказательство   

Чтобы вспоминать Успенского, нужно быть специалистом по математической логике. Просто для начала разговора.
Успенский это не предел.
Вот только что читала, как бабушка из моего города вначале перевела мошенникам 2 миллиона рублей деньгами через банкомат (как рука не устала деньги ложить и на кнопки нажимать), а потом ещё взяла кредит на полмиллиона и тоже перевела.
Ну кто такой Успенский супротив этого телефонного мошенника? Как плотник против столяра 

Цитата: Волод от февраля  1, 2022, 15:47
Если ни один из нулей не нулее другого, то можно  посмотреть к чему стремиться Х^х, когда Х-->0
Если не врёт мой калькулятор, то к 1.

Но F(x)^G(x) может быть любой, когда G(x) и F(x) → 0
(5^-1/х)^х = 0,2
(8^-1/х)^х = 0,125

О, Валентин Н понял пределы и раскрытие непоределённостей!

Цитата: Bhudh от февраля  9, 2022, 20:20
О, Валентин Н понял пределы и раскрытие непоределённостей!

Как бы классе в 9ом.

Цитата: _Swetlana от февраля  9, 2022, 19:31
Чтобы вспоминать Успенского, нужно быть специалистом по математической логике.

Вовсе нет

Цитата: _Swetlana от февраля  9, 2022, 19:31
Просто для начала разговора.

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

Цитата: _Swetlana от февраля  9, 2022, 19:31
Успенский это не предел.

На вашу полушуточную фразу я дал другую. Как говорится, великая мудрость это мудрость, отрицание которой тоже великая мудрость. 

Цитата: _Swetlana от февраля  9, 2022, 19:31
Ну кто такой Успенский супротив этого телефонного мошенника?

Ну да, у взгляда Успенского есть слабое место, когда нас могут убеждать ложные вещи. Выход - надо развивать мышление. Но у вашего взгляда тоже есть слабое место - когда требуют доказательства очевидных вещей, цепочка доказательств может уходить до бесконечности, как в том парадоксе Кэрролла, когда вместо того, чтобы применить очевидное правило вывода modus ponens, Ахилл уходит в бесконечные дебри рассуждений 

Цитата: Agnius от февраля 10, 2022, 08:55

Цитата: _Swetlana от февраля  9, 2022, 19:31
Чтобы вспоминать Успенского, нужно быть специалистом по математической логике.

Вовсе нет

Цитата: _Swetlana от февраля  9, 2022, 19:31
Просто для начала разговора.

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

Цитата: _Swetlana от февраля  9, 2022, 19:31
Успенский это не предел.

На вашу полушуточную фразу я дал другую. Как говорится, великая мудрость это мудрость, отрицание которой тоже великая мудрость. 

Цитата: _Swetlana от февраля  9, 2022, 19:31
Ну кто такой Успенский супротив этого телефонного мошенника?

Ну да, у взгляда Успенского есть слабое место, когда нас могут убеждать ложные вещи. Выход - надо развивать мышление. Но у вашего взгляда тоже есть слабое место - когда требуют доказательства очевидных вещей, цепочка доказательств может уходить до бесконечности, как в том парадоксе Кэрролла, когда вместо того, чтобы применить очевидное правило вывода modus ponens, Ахилл уходит в бесконечные дебри рассуждений 

Успенский был профессором той кафедры, которую я закончила. Но специализировалась не на математической логике, а на теории автоматов. Поэтому не берусь всякую хрень писать рассуждать о его книгах - образования не хватает.
Рада, что у вас с образованием всё хорошо сложилось   

Цитата: _Swetlana от февраля 10, 2022, 14:32
Успенский был профессором той кафедры, которую я закончила.

Круто, встретиться удалось? 

Цитата: _Swetlana от февраля 10, 2022, 14:32
Но специализировалась не на математической логике, а на теории автоматов.

Помнится, этой темой интересовался.

Цитата: _Swetlana от февраля 10, 2022, 14:32
Поэтому не берусь всякую хрень писать рассуждать о его книгах - образования не хватает.

Так я не рассуждал о его книгах 

Цитата: _Swetlana от февраля 10, 2022, 14:32
Рада, что у вас с образованием всё хорошо сложилось

Я вот тоже в школьные годы хотел пойти на математика, но все-таки выбрал физику 

Цитата: Agnius от февраля 10, 2022, 18:10

Цитата: _Swetlana от февраля 10, 2022, 14:32
Успенский был профессором той кафедры, которую я закончила.

Круто, встретиться удалось? 

Нет. Встретиться удалось только с А.А. Марковым-младшим, отцом советского конструктивизма. Поэтому я с тех и до сих пор конструктивист 

Если говорить об основаниях математики, что очевидно, а что не очень, то начинать надо не с комплексных чисел, а с натурального ряда.
Вот что очевидно мне (как любому другому конструктивисту) - только то, что можно построить. То есть все доказательства от противного мимо кассы.
И не абы как построить, а за конечное число шагов.
Можем мы построить весь бесконечный натуральный ряд за конечное число шагов?
Нит 
Значит, бесконечность для нас очевидно существует только как потенциальная, а не актуальная.
И всё было бы чудесно, но с конечным числом шагов можно только в теории алгоритмов строить разные математические модели алгоритма: детерминированную машину Тьюринга, частично-рекурсивную функцию, нормальный алгорифм Маркова.
А вот построить современный матанализ, пользуясь только конструктивным подходом, увы. нельзя. Почему нельзя - на эту тему написаны книги, не буду заниматься кратким пересказом.
Ну и, чтобы далеко к комплексным числам не ходить, иррациональное число корень квадратный из 2, диагональ единичного квадрата, Пифагор его уже знал, вполне себе существует как геометрический объект. Бесконечная непериодическая дробь, с бесконечным числом знаков после запятой, и все существуют одновременно.
Трудно быть конструктивистом   

Цитата: _Swetlana от февраля 10, 2022, 18:55
Встретиться удалось только с А.А. Марковым-младшим, отцом советского конструктивизма. Поэтому я с тех и до сих пор конструктивист 

А мне попадались одни математики неконструктивисты, с поговоркой где два конструктивиста, там три конструктивизма 

Цитата: _Swetlana от февраля 10, 2022, 18:55
Вот что очевидно мне (как любому другому конструктивисту) - только то, что можно построить.

Только тут все упирается в средства, одни признают одно, другие другое. Вы наверное не признаете существование счетной бесконечности? И там аксиомы выбора (даже счетной)?

Цитата: _Swetlana от февраля 10, 2022, 18:55
Значит, бесконечность для нас очевидно существует только как потенциальная, а не актуальная.

Вроде как дуализм пот. vs акт. бесконечности ушел в прошлое, в современной математике такого уже нет, есть просто бесконечность (счетная etc.). И даже если использовать эти понятия, то из потенциальной бесконечности следует актуальная, просто не все это хотят признать 

Цитата: _Swetlana от февраля 10, 2022, 18:55
И всё было бы чудесно, но с конечным числом шагов можно только в теории алгоритмов строить разные математические модели алгоритма: детерминированную машину Тьюринга, частично-рекурсивную функцию, нормальный алгорифм Маркова.

Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Цитата: Agnius от февраля 11, 2022, 11:31
Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Ну задачу нужно корректно формулировать, прежде чем предлагать её человечеству 
Что значит "из любого состояния есть переход в другое"? Переход из состояния в состояние определяется еще и входным сигналом.
При любом входном сигнале переходим из одного состояния в другое?
Если это не так, пишите: При некоторых входных сигналах есть переход из любого состояния в другое. 

Цитата: Agnius от февраля 11, 2022, 11:31
Вы наверное не признаете существование счетной бесконечности? И там аксиомы выбора (даже счетной)?

Мне это неочевидно, а признаю или не признаю - это дело десятое. Для теории алгоритмов она не нужна, там всё т.н. финитными средствами строится. Вот если бы, скажем, преподавала оптимальное управление, то пришлось бы поступать как генерал Чернота: пришла на лекцию - признала, вышла - снова в несознанку 

Цитата: Agnius от февраля 11, 2022, 11:31
Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Что значит "определить"? Есть какое-то более формальное условие?

Цитата: kemerover от февраля 11, 2022, 15:29

Цитата: Agnius от февраля 11, 2022, 11:31
Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Что значит "определить"? Есть какое-то более формальное условие?

Как я поняла, ДМТ описана как "чёрный ящик" и есть какие-то намёки о её структурной схеме.
Требуется описать её как "белый ящик", попросту говоря, описать её структурную схему (или системой команд, или диаграммой переходов).

Цитата: _Swetlana от февраля 11, 2022, 13:56
При некоторых входных сигналах есть переход из любого состояния в другое.

Да, так 

Цитата: _Swetlana от февраля 11, 2022, 14:04
пришла на лекцию - признала, вышла - снова в несознанку

Мне это напомнило серию south park про Докинза, посланного помощником учительнице биологии, не признающей ТЭ, которую вынуждена преподавать

Цитата: kemerover от февраля 11, 2022, 15:29
Что значит "определить"? Есть какое-то более формальное условие?

Определить - значит полностью задать устройство конечного автомата (черного ящика). За матчастью - в вики. Ну а если кратко, вам нужно для каждого внутреннего состояния (1 и 2) написать алгоритм действия. Алгоритм имеет вид - если подали x (0 или 1), то выдаем y (0 или 1) и переходим в состояние z (0 или 1). + еще надо учесть условие, что из любого состояния можно выйти

Если у вас на выходе всегда 0, как вы определите какие входы меняют состояние? Это какой-то слишком чёрный ящик.

Цитата: kemerover от февраля 11, 2022, 16:08
Если у вас на выходе всегда 0, как вы определите какие входы меняют состояние? Это какой-то слишком чёрный ящик.

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

Цитата: Agnius от февраля 11, 2022, 16:13
Да, есть функционально изоморфные состояния, поэтому нужно описать устройство такого автомата, который по произвольной входной строке x1x2... выдавал точно такую же строку, что и наш исходный черный ящик y1y2...

Зачем тогда вы вводите в заблуждение, говоря про "полностью задать устройство конечного автомата"?

Как можно работать с чёрным ящиком? Каждое новое число работает с предыдущим состоянием, и мы не можем обнулять состояние до изначального? В таком случае нельзя определить изначальное состояние. Или его не нужно определять?

Я думаю, что одна из причин, по которой никто не решил, это невнятность условий задачи.

Так. Уточняем дальше. Чему равна длина входного слова?
Один или два или n сигналов посылаем? И это случайная последовательность, или решающий задачу выбирает, что послать (в случае, если входное слово имеет длину больше 1)?
   

Цитата: kemerover от февраля 11, 2022, 16:44
Зачем тогда вы вводите в заблуждение, говоря про "полностью задать устройство конечного автомата"?

Тут можно уточнить - если алгоритмы для обоих состояний одинаковы, то нам не важна динамика переходов между внутренними состояниями.

Цитата: _Swetlana от февраля 11, 2022, 20:25
Так. Уточняем дальше. Чему равна длина входного слова?
Один или два или n сигналов посылаем?

Посылаем последовательно любое число сигналов, пока не решим задачу 

Цитата: _Swetlana от февраля 11, 2022, 20:25
И это случайная последовательность, или решающий задачу выбирает, что послать (в случае, если входное слово имеет длину больше 1)?

Сам выбирает

На входе 2 бита (входной сигнал и внутреннее состояние) и на выходе 2 бита (выходной сигнал и новое внутреннее состояние). Всего 4⁴=64 разных варианта устройства чёрного ящика.

Andrey Lukyanov
Во-первых, неправильно посчитали
Во-вторых, забыли условие При некоторых входных сигналах есть переход из любого состояния в другое. (или для любого состояния найдется сигнал, который это состояние сменит)

Цитата: Agnius от февраля 11, 2022, 11:31
..............
Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Цитата: _Swetlana от февраля 11, 2022, 20:25
Так. Уточняем дальше. Чему равна длина входного слова?
Один или два или n сигналов посылаем? И это случайная последовательность, или решающий задачу выбирает, что послать (в случае, если входное слово имеет длину больше 1)?
   

Что-то я не понял, в чём проблема? Я далёк от математики, но текст задачи я понимаю однозначно: "Сигнал - это либо "1", либо "0", а не какая-нибудь их последовательность или сочетание."

Цитата: Волод от февраля 12, 2022, 08:08

Цитата: Agnius от февраля 11, 2022, 11:31
..............
Я вот вспомнил одну свою задачку - Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Вроде как никто и не решил ее тогда 

Цитата: _Swetlana от февраля 11, 2022, 20:25
Так. Уточняем дальше. Чему равна длина входного слова?
Один или два или n сигналов посылаем? И это случайная последовательность, или решающий задачу выбирает, что послать (в случае, если входное слово имеет длину больше 1)?
   

Что-то я не понял, в чём проблема? Я далёк от математики, но текст задачи я понимаю однозначно: "Сигнал - это либо "1", либо "0", а не какая-нибудь их последовательность или сочетание."

Щас 
1. ДЕТЕРМИНИРОВАННАЯ МАШИНА ТЬЮРИНГА. ТЕЗИС ТЬЮРИНГА
1.1. Определение алгоритма
Центральным понятием Теории алгоритмов является определение или, лучше сказать, математическая модель алгоритма. Рассмотрим «наивное» определение алгоритма, которое обычно приводится в школьных учебниках.
1.   Алгоритм задаётся последовательностью инструкций.
2.   Алгоритм выполняется детерминировано, то есть для одинаковых данных выполняются одинаковые действия.
3.   Должен существовать вычислитель, способный выполнить указанные в алгоритме инструкции.
4.   Вычислитель должен иметь средства для хранения и отображения информации.
Иными словами, алгоритм – набор инструкций для формальной модели вычисления. Результативность алгоритма – желательное, но не обязательное свойство. Это важный момент. Алгоритм не обязан останавливаться, он может работать бесконечно («зациклиться»).
Чуть позже мы покажем, что математическая модель «Детерминированная машина Тьюринга» (ДМТ) не только полностью удовлетворяет школьному определению алгоритма, но и является вычислителем, способным выполнить все указанные в алгоритме инструкции. Далее будет показана эквивалентность двух математических моделей: вычислимой (частично-рекурсивной) функции и ДМТ.
Рассмотрим классификацию языков программирования по математической модели алгоритма. Существует три основные математические модели алгоритма: ДМТ, частично-рекурсивная (вычислимая) функция и исчисление предикатов первого порядка. Соответственно этим моделям языки программирования делятся на три группы: алгоритмические (или процедурные), функциональные и логические (рис. 1.1).
К алгоритмическим языкам относятся все языки, в которых программа состоит из последовательности команд. В эту группу попадают языки как «высокого», так и «низкого» уровня: Assembler, C++, Basic, Pascal и др.
Вторую группу образуют языки функциональные: Lisp, Haskell и др. В третьей группе находятся языки логические, наиболее популярным представителем которых является Prolog. Программа в таких языках представляет базу знаний, то есть состоит из истинных фактов и правил вывода; чтобы запустить программу на выполнение, нужно адресовать к базе знаний запрос или, как принято говорить, задать цель. Язык Prolog будет подробно изучаться в курсе «Логическое программирование».     
1.2. ДМТ и Тезис Тьюринга
1.2.1. ДМТ как структурная схема или «белый ящик»
ДМТ – это автомат, который имеет бесконечную ленту, управляющее устройство и считывающую/пишущую головку (рис. 1.2). Лента разделена на ячейки, в каждой ячейке записан либо пустой символ λ, либо символ некоторого конечного алфавита A. В каждый момент на ленте может быть только конечное число непустых символов. Управляющее устройство находится в одном из конечного множества состояний Q, среди них выделяются начальное q1 и заключительное qz. Считывающая головка в каждый момент обозревает ровно одну ячейку. Перед началом работы управляющее устройство ДМТ находится в начальном состоянии q1, а сама ДМТ находится на ячейке с первым непустым символом (обозревает первый непустой символ). Попав в заключительное состояние qz, ДМТ останавливается.

Один такт работы ДМТ можно описать следующим образом:
   Считать символ a_jиз текущей ячейки.
   Затереть текущий символ a_j  и, в зависимости от текущего состояния и прочитанного символа, записать вместо него новый символ〖 a〗_j^'.
   В зависимости от текущего состояния и прочитанного символа либо остаться на месте, либо сдвинутся на один шаг в соседнюю ячейку.
   В зависимости от текущего состояния q_iи прочитанного символа перейти в новое состояние q_i^'.
Таким образом, один такт работы ДМТ описывается командой q_i a_j  → q_i^' a_j^' d_k, где d_k={L,R,E}  (влево, вправо, на месте) – команда сдвига; q_(i ) и a_j  – текущее состояние и обозреваемый символ; q_i^( ') 〖и a〗_j^' – новое состояние и новый символ, записанный вместо a_j. Система всех команд вида q_i a_j  → q_i^' a_j^' d_k  образует функцию переходов δ.
Определение 1. Машиной Тьюринга называется совокупность 〈A,λ,Q,q_1,δ〉:
1. Алфавит A = {a1, ..., an} – множество символов данной машины Тьюринга; |A| ≥ 1. Иногда алфавит называют множеством внешних состояний машины Тьюринга.
2. Пустой символ λ   A.
3. Множество состояний Q = {q1, ..., qz}, |Q| ≥ 1. Это множество также называют множеством внутренних состояний машины Тьюринга.
4. Начальное состояние q_1 Q.
5. Функция переходов δ – множество всех команд вида q_i a_j→q_i^' a_j^' d_k, где q_(i ) и a_j – текущее состояние и обозреваемый символ; q_i^( ') 〖и a〗_j^' – новое состояние и новый символ, записанный вместо a_j; d_k={L,R,E} (влево, вправо, на месте) – команда сдвига.
Пример 1.1. Бесконечно двигаясь вправо, заполнить всю ленту единицами. A = {0, 1}.
Система команд ДМТ (1.1):

q_1 λ → q_1 1 R;
q_1 0 → q_1 1 R;
q_1 1 → q_1 1 R.   
(1.1)
Эту систему команд также можно задать с помощью таблицы (таблица 1.1):