0
Мне интересно это утверждение выше [название] истинно или нет.Докажите, что все нерекурсивные языки бесконечны
Это то, что у меня уже есть: Нерекурсивное средство неразрешимое.
Я прочитал это Are all infinite languages undecidable?
, который говорит:
Если язык неразрешима (нерекурсивна), должны быть некоторые строки сделать TM не halt.SO он должен иметь INFINITE ИХ, КОТОРЫЕ СДЕЛАТЬ ТЕМУ НЕИСПРАВНОСТИ.
Как это может подтвердить мое заявление [название]? Может ли кто-нибудь объяснить это мне более четко?
С благодарностью
пс. извините за путаницу. Да TM означает машину Тьюринга. И тоже быть ясным Мой вопрос: ВСЕ нерекурсивные языки Бесконечны?
У вас, кажется, есть несколько различных концепций. Вам интересно, если «нерекурсивный == бесконечный» или «нерекурсивный == неразрешимый» или «бесконечный == неразрешимый» или что-то еще полностью? Кроме того, не используйте аббревиатуры, которые вряд ли поймут люди (хотя я предполагаю, что «ТМ» означает «Машина Тьюринга», по крайней мере, на основе области вопросов). – twalberg
извините за путаницу. Да TM означает машину Тьюринга. И тоже быть ясным Мой вопрос: ВСЕ нерекурсивные языки Бесконечны? @twalberg – geasssos
Рассмотрим язык с алфавитом, состоящим из одного символа (называемого A) и одним произведением «P -> A». Язык принимает один вход, а именно A, и определенно нерекурсивный и определенно не бесконечен. Итак, нет, не все нерекурсивные языки бесконечны ... – twalberg