Цитата:
Автор оригинала: gromopetr
О, боги! Обобщать-то зачем?
|
Чтобы показать, что доказательства так не строятся
Цитата:
|
Вот лично мне очевидно, что можно написать на тьюринге интерпретатор С. И, если дать достаточно времени и какой-нибудь немаленький стимул, я могу это даже сделать.
|
С точки зрения теории, думаю, что можно. (Правда не уверен по части окружения выполнения, ну да я и стандарт в той его части не очень внимательно читал).
Но это теория. В теории можно, например, записать любое количество единиц - но на практике жизни на это может не хватить, если число взять достаточтно большим.
Машина Тьюринга, реализующая банальное сложение десятичных чисел будет иметь не менее 10 состояний и не менее 11 символов алфавита. А для всего С - 256 символов алфавита, а сколько состояний нужно, я даже предположить боюсь
)
Мораль: не всё выполнимо, что теоретически возможно
