Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет Misha Verbitsky ([info]tiphareth)
@ 2007-06-20 23:11:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Настроение: sick
Музыка:Куклы Напрокат - ПОВЕРИЛА
Entry tags:logic, math

тезис о формализации математики
Неожиданно сообразил:
а ведь убежденность в возможности формализации
математических доказательств
есть примерно то же самое,
что тезис Черча, утверждающий, что любой алгоритм (в
житейском смысле этого слова) сводится к
машинам Тьюринга. Сейчас считается, что это
определение алгоритма, в силу очевидной
недоказуемости тезиса. Люди пишут на языках
высокого уровня, предполагая, что перевести программу
на машинные коды или к машине Тьюринга или
свести доказательство к формальным языкам
при желании всегда можно. Хотя этого никто не
проверял, и проверить не может (трансляторы
в машинные коды существуют, но доказать их
безошибочность - задача такой же сложности,
как и проверка формализуемости доказательства).

Так вот, тезис о формализации математики имеет ту
же самую природу: на практике формализовать (или свести
к машине Тьюринга) можно только самые простые вещи,
но чтоб сомневаться в сводимости, нужно быть чем-то
вроде финитиста.


Привет



(Читать комментарии) - (Добавить комментарий)


[info]tiphareth
2007-06-21 01:50 (ссылка)
А вот нифига. Число Омега Хайтина невычислимо
теоретически, практически же очень просто вычисляется -
пишешь N случайных программ, запускаешь, считаешь процент тех,
которые остановились за K ходов, устремляешь N и K к
пределу. Типа метод Монте-Карло.

Ну или еще проще - воспользуйся тем, что множество
рациональных чисел меньше Омеги перечислимое.

Такие дела
Миша

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]gaz-v-pol.livejournal.com
2007-06-21 11:19 (ссылка)
Забавно, а как так может быть? Вообще, казалось бы, множество программ счетно, поэтому из этого множество нельзя случайно выбрать одну (или 100) программ ?

Кроме того, не вполне ясно, как проверять, является ли данный конкретный набор символов текстом программы ?

(Ответить) (Уровень выше) (Ветвь дискуссии)


[info]polytheme
2007-06-22 11:25 (ссылка)
http://en.wikipedia.org/wiki/Chaitin_Omega
:)
привет, Сережа

(Ответить) (Уровень выше)


[info]polytheme
2007-06-22 11:23 (ссылка)
а, вы опять шутите.

(Ответить) (Уровень выше)


(Читать комментарии) -