Является ли С без goto тьюринг-полным?

[guz]

Дано:
1) Основываясь на Википедии тьюринг-полный язык программирования (такого термина вообще-то нет, есть "исполнитель (множество вычисляющих элементов)", но это видимо одно и то же) этот тот, на котором можно запрограммировать любую вычислимую функцию. Как ни старался, не осилил понятие вычислимости. (Может кто объяснит?)
2) Все тру отцы программисты утверждают, что goto - это плохо.
3) Меж тем наличествует море алгоритмов, которые нельзя запрогать без goto, не изменив сам алгоритм (без дополнительных флагов и пр.).

Вопрос 1: Существует ли такой алгоритм с goto, который нельзя преобразовать в эквивалентный без goto (путём добавления флагов и пр.)?

Вопрос 2: В чём различие между сабжем и первым вопросом?

[Stilet]

море алгоритмов

Алгоритмы в студию.

[guz]

Может я не уместно употребил слово "алгоритм", я имел в виду что-то вроде алгоритмичской конструкции на С с одним входом и одним выходом.
Лучше было бы конечно нарисовать, но что-то лень, напишу скелеты кода:

Например такая "бабочка":

if(){

	while(){

		if() goto label2;
		label1:	

	}

}else{

	while(){

		if() goto label1;
		label2:
	
	}

}

Или такая "ерунда":

if(){
	if(){
		
	}else{	
		
		label:
		
	}
}else{
	goto label;
}

[guz]

Знаете, в процессе обсуждения пришел к выводу, что перепутал понятия алгоритм с реализацией алогритма, когда говорил про море. Прошу прощения.

Тем не менее, даже если полностью вычеркнуть "Дано", ответы на вопросы 1 и 2 остаются.

[Stilet]

Например такая "бабочка":

Такая бабочка в принципе "невозможна", ибо это верный крах системы.
Так что goto тут ни при чем.

[guz]

Ой, да что Вы говорите!

Два потока, читаем, обрабатываем, пишем, переключаемся между потоками по команде, которую получаем из потока, и после переключения должны отправить приглашение в тот поток, на который переключились. Как это сделать без переменной-идентификатора потока и флага отправки приглашения?
Я, конечно, понимаю, что проблема надуманная, но дело ведь не в "бабочке".
И за море я извинился.
А вопрос-то остался открытым.

ЗЫ: Да, а что по поводу второго примера?

[Stilet]

Два потока

Где? Последовательное переключение между блоками программы уже потоками называться стало?
С таким же успехом можно написать понадежнее

void first(){	printf("1");}
void second(){	printf("2");}

int _tmain(int argc, _TCHAR* argv[])
{
	while(true){first();second();}

	return 0;
}

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

а что по поводу второго примера?

Этого который:

Или такая "ерунда":

Запусти его. Он выполнится только один раз.
IF() тут точно не помошник. с while() тебе повезло.

Все тру отцы программисты утверждают, что goto - это плохо.

Ерунда. JMP в Ассемблере никогда не отменят.

По сабжу ИМХО понятие "вычислимости" предполагает любые действия процессора, ибо при любых действиях в нем происходят вычисления.

[Enchance]

Цитата:

if(){
	if(){
		
	}else{	
		
		label:
		
	}
}else{
	goto label;
}

А зачем кому-то может понадобиться телепортироваться внутрь if-ов?! Какая реальная потребность может заставить пойти на это? Имхо, здесь через функции можно такое реализовать.
Лично я слышал, что доказано, язык С - тьюринг-полный и без goto (пруф не просите, я давно это читал и пруфа у меня нету). Goto плох считается потому, что очень трудно читать код, в котором слижком много переходов, но иногда использование оператора безусловного перехода позволяет увеличить быстродействие программы, и сократить время написания программы.

Кстати, а как реализовать такое без goto?

main:
cin >> i;
if (i==1) { [instruction1]; goto main;}
if (i==2) { [instruction2]; goto main;}
if (i==3) { [instruction3]; goto main;}
if (i==4) { [instruction4]; goto main;}

if (i==N) { [instructionN]; goto quit;}
quit:

[Гром]

Кстати, а как реализовать такое без goto?

bool quit = false;
while (!quit)
 {
 cin >> i;
 if (i==1) { [instruction1];}
 if (i==2) { [instruction2];}
 if (i==3) { [instruction3];}
 if (i==4) { [instruction4];} 
 }

Допустим, что внутри [] может меняться i и потому обойдемся без else и switch.

[Morkonwen]

Или такая "ерунда":

if(усл1){
	if(усл2){
		блок1
	}else{	
		 блок2
		label:
                      блок3
		
	}
}else{
            блок4
	goto label;
            здесь пусто, т.к. после goto
}

[/QUOTE]

можно переписать и без go to

мне мой вариант кажется понятнее=)

if(улс1&&улс2)
{
   блок1
} else 
{
      if (!(усл1))

     {
		 блок4
     } else 
    {
                      блок2
    }

блок3
}