|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
04.11.2010, 16:11 | #1 |
Пользователь
Регистрация: 29.10.2010
Сообщений: 29
|
Является ли С без goto тьюринг-полным?
Дано:
1) Основываясь на Википедии тьюринг-полный язык программирования (такого термина вообще-то нет, есть "исполнитель (множество вычисляющих элементов)", но это видимо одно и то же) этот тот, на котором можно запрограммировать любую вычислимую функцию. Как ни старался, не осилил понятие вычислимости. (Может кто объяснит?) 2) Все тру отцы программисты утверждают, что goto - это плохо. 3) Меж тем наличествует море алгоритмов, которые нельзя запрогать без goto, не изменив сам алгоритм (без дополнительных флагов и пр.). Вопрос 1: Существует ли такой алгоритм с goto, который нельзя преобразовать в эквивалентный без goto (путём добавления флагов и пр.)? Вопрос 2: В чём различие между сабжем и первым вопросом? Последний раз редактировалось guz; 04.11.2010 в 16:20. |
04.11.2010, 16:36 | #2 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
I'm learning to live...
|
|
04.11.2010, 16:52 | #3 |
Пользователь
Регистрация: 29.10.2010
Сообщений: 29
|
Может я не уместно употребил слово "алгоритм", я имел в виду что-то вроде алгоритмичской конструкции на С с одним входом и одним выходом.
Лучше было бы конечно нарисовать, но что-то лень, напишу скелеты кода: Например такая "бабочка": Код:
Код:
Последний раз редактировалось guz; 04.11.2010 в 16:55. |
04.11.2010, 16:59 | #4 |
Пользователь
Регистрация: 29.10.2010
Сообщений: 29
|
Знаете, в процессе обсуждения пришел к выводу, что перепутал понятия алгоритм с реализацией алогритма, когда говорил про море. Прошу прощения.
Тем не менее, даже если полностью вычеркнуть "Дано", ответы на вопросы 1 и 2 остаются. |
04.11.2010, 17:30 | #5 | |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
Так что goto тут ни при чем.
I'm learning to live...
|
|
04.11.2010, 18:15 | #6 |
Пользователь
Регистрация: 29.10.2010
Сообщений: 29
|
Ой, да что Вы говорите!
Два потока, читаем, обрабатываем, пишем, переключаемся между потоками по команде, которую получаем из потока, и после переключения должны отправить приглашение в тот поток, на который переключились. Как это сделать без переменной-идентификатора потока и флага отправки приглашения? Я, конечно, понимаю, что проблема надуманная, но дело ведь не в "бабочке". И за море я извинился. А вопрос-то остался открытым. ЗЫ: Да, а что по поводу второго примера? |
04.11.2010, 19:27 | #7 | ||||
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Цитата:
С таким же успехом можно написать понадежнее Код:
Но это не два разных потока, тут параллельными вычислениями и не пахнет. Проблема действительно надуманная. Цитата:
Цитата:
IF() тут точно не помошник. с while() тебе повезло. Цитата:
По сабжу ИМХО понятие "вычислимости" предполагает любые действия процессора, ибо при любых действиях в нем происходят вычисления.
I'm learning to live...
|
||||
04.11.2010, 22:21 | #8 |
Пользователь
Регистрация: 20.10.2009
Сообщений: 23
|
Цитата:
Код:
Лично я слышал, что доказано, язык С - тьюринг-полный и без goto (пруф не просите, я давно это читал и пруфа у меня нету). Goto плох считается потому, что очень трудно читать код, в котором слижком много переходов, но иногда использование оператора безусловного перехода позволяет увеличить быстродействие программы, и сократить время написания программы. Кстати, а как реализовать такое без goto? Код:
|
04.11.2010, 23:37 | #9 | |
Старожил
Регистрация: 21.03.2009
Сообщений: 2,193
|
Цитата:
Код:
Простые и красивые программы - коды программ + учебник C++
Создание игры - взгляд изнутри - сайт проекта Тема на форуме, посвященная ему же |
|
05.11.2010, 04:37 | #10 |
Пользователь
Регистрация: 27.06.2010
Сообщений: 44
|
Или такая "ерунда":
Код:
можно переписать и без go to мне мой вариант кажется понятнее=) Код:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
тьюринг в delphi | gulsana-89@mail.ru | Помощь студентам | 0 | 16.09.2010 14:12 |
Связь двух книг с полным форматированием | tns-ka | Microsoft Office Excel | 7 | 14.05.2010 07:01 |
помогите решить задачи на паскале, если можно с полным решением | вадимкО | Помощь студентам | 4 | 13.12.2009 13:04 |
Поиск с полным совподением. | Rom1k06 | Microsoft Office Excel | 2 | 13.10.2009 10:27 |
экспорт отчетов аксесс в эксель с полным форматированием | kate158 | Помощь студентам | 1 | 11.03.2009 17:52 |