Телеграмм чат группы compilerdev страница 761

2020 January 27

YS

Yaroslav Schekin in Compiler Development

MaxGraey

Нет. DFA например не Тьюниг полные но подвержены halting problem

("Догоняя" историю чата) Что?!
Повторили бы Вы теорию. ;)

источник

11:49пожаловаться #1

AT

Alexander Tchitchigin in Compiler Development

Andrei Kurosh

Так, погодите, давайте синхронизируемся по пунктам. Я перестаю успевать за вашим полетом мысли :)

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

Нет, не может. Никакая физически реализуемая вычислительная система не может являться полной по Тьюрингу в силу конечности размеров.

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

источник

11:52пожаловаться #2

AK

Andrei Kurosh in Compiler Development

Alexander Tchitchigin

Нет, не может. Никакая физически реализуемая вычислительная система не может являться полной по Тьюрингу в силу конечности размеров.

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

Тогда возникает следующий вопрос - какой смысл от спецификации, которую нельзя реализовать? )

источник

11:55пожаловаться #3

YS

Yuriy Syrovetskiy in Compiler Development

Alexander Tchitchigin

Нет, не может. Никакая физически реализуемая вычислительная система не может являться полной по Тьюрингу в силу конечности размеров.

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

Тьюринг не требует бесконечность. он требует бесконечность ИЛИ возможность добавлять память, когда понадобится

источник

11:55пожаловаться #4

M

MaxGraey in Compiler Development

Yaroslav Schekin

("Догоняя" историю чата) Что?!
Повторили бы Вы теорию. ;)

В чем именно? Что DFA тьюринг полные? Или что они не подвержены проблеме останова?

источник

11:56пожаловаться #5

AK

Andrei Kurosh in Compiler Development

Вообще я сильно сомневаюсь, что например в спецификации Си упомянута\подразумевается бесконечная память, т.к. размер указателя вполне конечен

источник

11:57пожаловаться #6

BD

Berkus Decker in Compiler Development

Alexander Tchitchigin

Тогда давате выберем критерием простоту написания специализатора на заданном ЯП. 😂

Дааа)

источник

11:57пожаловаться #7

YS

Yuriy Syrovetskiy in Compiler Development

Andrei Kurosh

Вообще я сильно сомневаюсь, что например в спецификации Си упомянута\подразумевается бесконечная память, т.к. размер указателя вполне конечен

Си не полный, уже обсуждали несколько раз

источник

11:57пожаловаться #8

AK

Andrei Kurosh in Compiler Development

Yuriy Syrovetskiy

Си не полный, уже обсуждали несколько раз

Вот мы только что пришли к выводу, что полных-то вообще не существует

источник

11:58пожаловаться #9

AT

Alexander Tchitchigin in Compiler Development

Andrei Kurosh

Тогда возникает следующий вопрос - какой смысл от спецификации, которую нельзя реализовать? )

Это, безусловно, интересный философский вопрос, который ведёт к более общему: какой смысл в моделях (в особенности - математических), если они не в полной мере соответствуют действительности?

Не знаю, какой ответ даёт на него философия, но на практике мы знаем, что от моделей много пользы в разных аспектах, при этом именно благодаря тому, что они не во всех деталях описывают реальность (aka абстрагируют её). 😉

источник

11:58пожаловаться #10

BD

Berkus Decker in Compiler Development

Andrei Kurosh

Вот мы только что пришли к выводу, что полных-то вообще не существует

Через три года в компиляторном чатике начали что-то подозреватт

источник

11:58пожаловаться #11

YS

Yuriy Syrovetskiy in Compiler Development

Andrei Kurosh

Вот мы только что пришли к выводу, что полных-то вообще не существует

в теории существуют

источник

11:58пожаловаться #12

AT

Alexander Tchitchigin in Compiler Development

Yuriy Syrovetskiy

Тьюринг не требует бесконечность. он требует бесконечность ИЛИ возможность добавлять память, когда понадобится

Это похоже на разницу между актуальной и потенциальной бесконечностью. Я разницы между ними не вижу.

источник

11:59пожаловаться #13

AT

Alexander Tchitchigin in Compiler Development

Andrei Kurosh

Вот мы только что пришли к выводу, что полных-то вообще не существует

Java? C#? Haskell? 😊

источник

12:00пожаловаться #14

YS

Yuriy Syrovetskiy in Compiler Development

Alexander Tchitchigin

Это похоже на разницу между актуальной и потенциальной бесконечностью. Я разницы между ними не вижу.

не похоже, а она и есть. разница как раз на практике

источник

12:00пожаловаться #15

YS

Yaroslav Schekin in Compiler Development

MaxGraey

В чем именно? Что DFA тьюринг полные? Или что они не подвержены проблеме останова?

Все DFA останавливаются, очевидно.

источник

12:00пожаловаться #16

YS

Yuriy Syrovetskiy in Compiler Development

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

источник

12:01пожаловаться #17

AT

Alexander Tchitchigin in Compiler Development

Yuriy Syrovetskiy

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

И теоретически НЕ полным, потому что (доступные) пространство и энергия конечны? 😂

источник

12:02пожаловаться #18

AK

Andrei Kurosh in Compiler Development

Alexander Tchitchigin

Это, безусловно, интересный философский вопрос, который ведёт к более общему: какой смысл в моделях (в особенности - математических), если они не в полной мере соответствуют действительности?

Не знаю, какой ответ даёт на него философия, но на практике мы знаем, что от моделей много пользы в разных аспектах, при этом именно благодаря тому, что они не во всех деталях описывают реальность (aka абстрагируют её). 😉

Тут есть два момента, с которыми я не согласен

источник

12:06пожаловаться #19

YS

Yuriy Syrovetskiy in Compiler Development

Alexander Tchitchigin

И теоретически НЕ полным, потому что (доступные) пространство и энергия конечны? 😂

мы это точно знаем?

источник

12:07пожаловаться #20