Проблема останова. В чём противоречие?

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

0

Сообщение от Aycon ок, я заменил на true и программа не зависла

Не вижу, где Вы вызываете функцию.

з.ы. В c# вместо зависания будет SOE. Чтобы реально зависла, нужно переписать на F# или заменить рекурсию циклом (как было в предыдущем примере).

0

Shamil1, вы передали в text программный код, в котором нет вызова. Если вы хотите, чтобы был осуществлён вызов - добавьте его в text. Это ведь совершенно другая программа. Как я могу на своё усмотрение менять, предоставленное ВАМИ содержимое переменной text? Как Оракул должен был понять, что вы хотите вызов какой-то функции в text, если вы сами это не указали?

Добавлено через 3 минуты
Shamil1, или, как вариант предоставьте не функцию, а её содержимое. Только таким образом, чтобы оно компилировалось.

Добавлено через 4 минуты
Shamil1, проблема в том, что чтобы случилось то, что вы хотите - нужно проинициализировать text внутри text, а это невозможно, так как программа получится бесконечной. Это справедливо для любого языка, не только c#. Это является строгим индуктивным доказательством, что функция prog в общем случае не реализуема ни для одного потенциального Оракула. Прислушайтесь, подвергните это анализу, прошу вас. Я полагаю, что вы просто слепо следуете авторитету.

Добавлено через 22 минуты
Shamil1, мы можем бесконечно спорить об этом

0

Сообщение от Aycon вы передали в text программный код, в котором нет вызова. Если вы хотите, чтобы был осуществлён вызов - добавьте его в text

Я предоставляю процедуру (код) и её вход (что угодно). Оракул должен мне ответить, завершится ли выполнение этой процедуры с этими входными данными.
Делается это так:

Сообщение от Aycon нужно проинициализировать text внутри text,

Кому нужно? Мне не нужно. Если это нужно Вам, то это Ваши проблемы. Я код предоставил. Код компилируется. На входные данные моей функции (которые случайно совпали с её кодом) вообще нет никаких ограничений. Какие ко мне вопросы?

0

Shamil1,

Я предоставляю процедуру (код) и её вход (что угодно). Оракул должен мне ответить, завершится ли выполнение этой процедуры с этими входными данными.

А как тогда выглядит процедура, в которой объявляется, но не вызывается Prog? Я вижу объявление некоей функции Prog. И само по-себе это объявление - является процедурой, которую вы сообщаете Оракулу. Это то, с чем он работает. По факту - процедура в text останавливается всегда. Если вы подразумевали, что что-то в строке будет интерпретированно как функция и вызвано, то вы должны явно указать это в рамках процедуры, которую вы передаёте в текст.
Если вы считаете, что это не так, тогда ответьте на следующие вопросы, пожалуйста:
1) Как тогда выглядит процедура, в которой объявляется, но не вызывается Prog?
2) Почему я должен вызвать именно Prog? Почему, например, не Oracle(text, text);?
Если вы подразумеваете вызов - пишите вызов. Оракул не гадалка, на самом деле.

Делается это так:

Где написано, что это именно так должно быть? Это вы предложили такую условность, я лично 10 раз уже сказал, что текст (кода c#) не является строго полным описанием процедуры. Пример - выше. Только вы игнорируете это факт.

нужно проинициализировать text внутри text, Кому нужно? Мне не нужно. Если это нужно Вам, то это Ваши проблемы

Вы сами сказали, что нужно вызвать процедуру. Я сказал, что в text об этом ничего не сказано. Так что это вам нужно, а не мне.

Добавлено через 7 минут
Shamil1, если хотите однозначности - передавайте в Оракула набор символов Brain****. Программа на брейнфаке всегда корректна, если она конечна, состоит из набора символов из 8 буквенного алфавита инструкций, а также имеет конечный набор символов в качестве ввода. Который, кстати, непосредственно передаётся в качестве единственного параметра.

Добавлено через 31 минуту
Shamil1,

Сообщение от Aycon  ок, я заменил на true и программа не зависла Не вижу, где Вы вызываете функцию.

Добавлено через 2 минуты
Shamil1, оракул может вообще не вызывать функцию в процессе работы.

0

Сообщение от Aycon А как тогда выглядит процедура, в которой объявляется, но не вызывается Prog?

Не знаю, про какую процедуру Вы говорите и зачем она Вам нужна.

Сообщение от Aycon Я вижу объявление некоей функции Prog. И само по-себе это объявление - является процедурой, которую вы сообщаете Оракулу.

Код функции Prog - это описание функции Prog. Вопрос к Оракулу именно про эту процедуру - остановится она или нет, если ей на вход подать строку. Строка совершенно случайно совпадает со строкой, содержащей код функции Prog.

Сообщение от Aycon 1) Как тогда выглядит процедура, в которой объявляется, но не вызывается Prog?

Не понимаю, о какой процедуре Вы говорите.

Сообщение от Aycon 2) Почему я должен вызвать именно Prog? Почему, например, не Oracle(text, text);?

Не понимаю, почему Вы решили, что Вы должны вызывать Prog. Не надо её вызывать. Просто скажите, что вернёт Oracle(text, text).

Сообщение от Aycon я лично 10 раз уже сказал, что текст (кода c#) не является строго полным описанием процедуры. Пример - выше.

Вы можете ещё 100 раз это сказать, но это ничего не изменит.
От чего, кроме кода Prog и входного параметра text зависит результат вызвова Prog(text)?

Сообщение от Aycon Вы сами сказали, что нужно вызвать процедуру.

Оракулу НЕ нужно вызывать процедуру. Процедуру я предлагаю вызвать Вам (а не Оракулу), чтобы на практике убедиться, что ответ Оракула неверный. А можете и не вызывать. Это и без вызова очевидно - достаточно взглянуть на код.

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

0

Shamil1,

Не знаю, про какую процедуру Вы говорите и зачем она Вам нужна.

Не понимаю, о какой процедуре Вы говорите.

Подумайте, пожалуйста, интенсивнее и поймите. Это же ответ на вопрос, почему то, что вы передаёте в Оракул - не исчёрпывающее описание функции.

2) Почему я должен вызвать именно Prog? Почему, например, не Oracle(text, text);? Не понимаю, почему Вы решили, что Вы должны вызывать Prog. Не надо её вызывать. Просто скажите, что вернёт Oracle(text, text).

Я имел в виду, какую из представленных в исходном коде нужно подвергнуть анализу? В text находятся две функции. Оракул в данном случае - встроенная функция, да, но можно ли использовать этот факт для автоматического использования? Как иначе вы сможете предать анализу встроенную функцию, без указания внешней функции? Я настаиваю на то, чтобы вызов Prog был внутри text, потому что в таком случае при слепом запуске кода из text автоматически вызывается необходимая функция. Именно ЭТО и приводит к остановке или входу в бесконечный цикл Процедуры, Которую вы передаёте в Оракул. Именно это и должен в конечном итоге анализировать Оракул. А код, который вы приводите в text просто останавливается Всегда. И его анализ не вызывает вопросов.

Добавлено через 5 минут
Shamil1, если вы считаете, что я не прав - нет ничего проще, чем предоставить код на брейнфак. Сразу же отпадает путаница с функциями, классами и прочими синтаксическими усложнениями. Есть только процедура в чистом виде. Ну же, там всего лишь один цикл и один условный оператор. Я не думаю, что это неподъёмная задача для вас. Если только функция Prog в принципе может быть написана на Тьюринг-полном ЯП.

Добавлено через 3 минуты
Shamil1, вы допускаете вероятность того, что Prog не может быть написана на брейнфак? Даже если на ленте будет располагаться готовый код Oracle как я предлагал ранее - 10 ячеек на исходный код для вызова и в 11 ячейку записывается результат?

0

Сообщение от Aycon Это же ответ на вопрос, почему то, что вы передаёте в Оракул - не исчёрпывающее описание функции.

Это не ответ на вопрос. Что, по Вашему мнению, является исчёрпывающим описанием функции?

Сообщение от Aycon Я имел в виду, какую из представленных в исходном коде нужно подвергнуть анализу? В text находятся две функции.

Откройте справочник по языку и посмотрите, как выглядит описание/объявление функции. Затем подумайте, пожалуйста, интенсивнее и попробуйте понять, описание какой функции содержит текст.

Сообщение от Aycon Я настаиваю на то, чтобы вызов Prog был внутри text

Вы можете настаивать на чём угодно, но есть правила описания функций.
Интересно, если я переименую функцию в main, Вы попросите от меня код операционной системы?

Сообщение от Aycon Именно это и должен в конечном итоге анализировать Оракул.

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

Сообщение от Aycon нет ничего проще, чем предоставить код на брейнфак

Если для Вас это так просто, то перепишите на брейнфак.

Сообщение от Aycon Если только функция Prog в принципе может быть написана на Тьюринг-полном ЯП.

Очевидно, что может. Более того, она уже написана.

0

Shamil1,

Это не ответ на вопрос. Что, по Вашему мнению, является исчёрпывающим описанием функции?

Исходный код этой функции на брейнфак.

0

Сообщение от Aycon Исходный код этой функции на брейнфак.

Глупое требование. Вы бы ещё код на Malbolge попросили.

0

Shamil1, объясните, пожалуйста, почему глупое?
И это не требование, это один из вариантов однозначного описания процедуры на мой взгляд.

0

Сообщение от Aycon объясните, пожалуйста, почему глупое?

На брейнфаке трудно писать и трудно понять, что делает программа.

Сообщение от Aycon И это не требование, это один из вариантов однозначного описания процедуры на мой взгляд.

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

0

Shamil1, не настолько, чтобы не переписать пару statesment из функции в 4-8 строк. А понять что она делает - очень легко. Брейнфак часто используют для подобных задач, поскольку она (программа на брейнфаке) очень минималистична (проще ассемлера), но при этом полна по тьюрингу.

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

Тем проще будет переписать её на брейнфак. Удачи. Хотя, я полагаю, вы или кто либо ещё уже попытались и ничего не вышло.

0

Сообщение от Aycon очень минималистична (проще ассемлера), но при этом полна по тьюрингу.

Субъективно. На мой взгляд ассемблер проще. Еще проще паскаль или си.

Известная теорема:

Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот.

Что, сложно на си или паскале написать машину Тьюринга? Да ассемблер то попроще брейнфака будет, тем более, что можно взять макро-ассемблер.

0

Shamil1, вы передаёте исходный текст функции, которая зависит от аргумента, чтобы проанализировать её выполнение. Эта функция зависит от результата выполнения самой себя. Она рекурсивная. Это не видно явно, но станет видно, если вы попытаетесь проинициализировать text внутри text. А не вызывает это ошибку компиляции, потому что вы передаёте строку и объявляете контракт (предусловие), что в строке находится исходный код корректной функции, все необходимые переменные для которой определены. Этот контракт вы (подразумевается) соблюдаете, вызывая функцию Oracle().

Этот код тоже скомпилируется:
Но упадёт на этапе выполнения и не потому что функция ToInt32(string val) некорректно реализованна или не существует, а потому что программист - допустил ошибку в силу юного возраста и неокрепшего ума.

Понимаете о чём я говорю? Вот поэтому то, я и настаиваю на коде брейнфак, потому что там просто не удастся так схалявить. Сам синтаксис языка это не позволит, если вы будете соблюдать синтаксис брейнфак, соглашение о конечности исходного кода и строки ввода, и так далее. Элементарные вещи.

Если бы вы мне здраво ответили, как Оракул должен угадать содержимое text внутри text - ничего этого не было бы необходимо. С рассудительным человеком и общаться на порядок проще, приятней и эффективнее. А ваш троллинг меня с самого начала топика раздражает, ведь начинал я максимально корректно.

Добавлено через 6 минут
vantfiles, прочитайте этот ответ, пожалуйста.

По аналогии, мистер Shamil1, заявляет мне, что-то вроде:
"Я вызову эту
строку и мне по-барабану, как конвертер должен справиться с этим. Я передаю в него описание числа, и если он не может справиться с анализом, то это проблемы его реализации (программиста). Либо конвертер не существует. "
Вдумайтесь.

0

А доказательство, по-моему оно очевидно:

Докажем от противного. Предположим существует такая полностью вычислимая функция halts(f), которая возвращает true, если функция f остановится когда-либо, и false, если функция f никогда не остановится.
Рассмотрим следующую функцию g
halts(g) должна возвращать либо true, либо false.

Если halts(g) вернула true, то g никогда не остановится, получили противоречие
Если halts(g) вернула false, то g остановится, получили противоречие

О чем можно говорить 8 экранов - загадка.

0

vantfiles, я предложил обход этой проблемы. И да, он существует, если глубина рекурсии конечна. Если же глубина рекурсии бесконечна, то такой вызов нельзя проинициализировать. Обратное мне пытается доказать мистер Shamil1. Либо не доказать, а оспорить моё утверждение, что такой вызов нельзя проинициализировать. На псевдокоде это возможно, но ни на каком реальном языке. Потому что программа будет бесконечна в длинну. (Программа (исходный код) конечна по определению)

0

Сообщение от Aycon не настолько, чтобы не переписать пару statesment из функции в 4-8 строк.

Это на C# "пара инструкций", а на брейнфак, возможно, будут тысячи инструкций. Я не умею программировать на брейнфак и учиться не собираюсь.

Сообщение от Aycon А понять что она делает - очень легко.

Не очень легко, а практически невозможно (без использования специальных инструментов).
Цитата: "Программы на языке Brain**** писать сложно, за что его иногда называют языком для мазохистов."

Сообщение от Aycon Брейнфак часто используют для подобных задач

Не слышал, чтобы брейнфак использовали для подобных задач.

Сообщение от Aycon поскольку она (программа на брейнфаке) очень минималистична (проще ассемлера)

Минималистична - не значит проще.
В Malbolge тоже всего 8 инструкций. Но, насколько я знаю, до сих пор ни один человек не смог написать ни одной программы на этом языке.

0

vantfiles, вот как должна выглядеть сигнатура G на языке c#:
Самое забавное, что тут и Оракул не нужен, чтобы показать, что G невозможна.

Добавлено через 1 минуту
Shamil1,

Цитата: "Программы на языке Brain**** писать сложно, за что его иногда называют языком для мазохистов."

Юмор? Не, не слышал.

0

Сообщение от Aycon /* в периоде */

А откуда периоды, если в качестве параметра в ф-цию G следует передать всего лишь ее собственный текст?

Добавлено через 2 минуты

Сообщение от Aycon Юмор? Не, не слышал.

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

0

Shamil1, малболг разрабатывался как язык на котором писать сложнее всего, потому что после выполнения каждой инструкции весь исходный код шифруется (кодируется).
Брейнфак разрабатывался, как язык с самой простой реализацией интерпретатора. Его используют в теории вычислимости, для подтверждения теорем в науке теория алгоритмов, а также для проверки гипотез, связанных с программированием и метапрограммированием. На брейнфаке, элементарно, проще всего, например перебрать все листинги программ, не превышающих 8 символов исходного кода. Попробуйте на c# перебрать все программы, состоящие максимум из 8 символов (символы в контексте языка программирования, а не одна буква. Это все ключевые слова, операторы, выражения и много чего ещё) их десятки. А даже 20^8 перебрать нереально. Даже если считать, что каждый листинг обрабатывается не дольше, чем инкремент. Я не говорю, что это нереально, но на брейнфаке существенно СУЩЕСТВЕННО проще.

0