>>5209> Сам придумал?
Я уже примерно догадываюсь, что имеешь ввиду какую-то хеш-функцию. Если это некоторая хеш-функция или типа того, то она будет обрабатывать вохдные данные еще до завершения ввода, как бы "ужимать" их. Если программа ограничена в памяти, то что бы мы туда не вводили, программа по любому будет иметь ограниченое количество состояний на момент окончания ввода. Следовательно, у нее будет ограниченое количество вариантов "ответа".
#include <stdio.h>
int main(void)
{
int a=0;
unsigned char c=0, g;
while (a != -1)
do
{
c = a ^ c;
g = c + a;
a = getchar();
}
while (a != -1);
//ВВОД ОКОНЧЕН
c = c - g; //допустим, мы совершаем какие-то еще действия
printf (" %d", c);
return 0;
} нам абсолютно неважно, сколько времени мы потратили на вбивание символов в эту программу. После ЕOF, переменная
c и
g будет иметь значение от 0 до 255. Программа какбы ужимаем входные данные в эти две переменные. Вот тебе эквиавлент этой программы без ужимания ввода в две переменные, а просто тупо вводя эти две переменные. Таким образом, задача сводится к задаче нахожнения вот этого:
#include <stdio.h>
int main(void)
{
unsigned char c, g;
g = getchar();
с = getchar();
//ВВОД ОКОНЧЕН
c = c - g; //допустим, мы совершаем какие-то еще действия
printf (" %d", c);
return 0;
} а тут уже не какой угодно кусок данных. Какой угодно кусок данных просто становится этими двумя переменными. Понимаешь?
Ок, может ты имел ввиду программу, которая непрерывно обрабатывает поступающую в него информацию и начинает выводить результат до окончания ввода? Например дельта-кодирование
#include <stdio.h>
int main(void)
{
int a=0;
unsigned char b=0;
while (a != -1)
do
{
b = a;
a = getchar();
putchar (a-b);
}
while (a != -1);
return 0;
} Эта задача то же самое, что многократное решение задачи вида:
#include <stdio.h>
int main(void)
{
unsigned char b, a;
b = getchar();
a = getchar();
putchar (a-b);
return 0;
} до наступления EOF
И у нас тут будет две ограниченые переменные
a и
b. И вывод на каждом шаге цикла будет зависеть от них. Улавливаешь? Или тебе нужно расписать настолько подробно, чтобы даже имбецил понял?
> И даже в таких идеальных условиях теоремы Тьюринга и Райса неразрешимы.
Именно в таких идеальных условиях теоремы Тьюринга и Райса неразрешимы. Если ограничить память, то они вполне разрешимы.
