Wiem trochę o tym, co jest turing-machine i a turing-complete język, ale aby lepiej zrozumieć, czy ktoś mógłby podać przykłady języków, które nie są kompletne? (może nawet maszyny, które nie są Turingiem?)
Odpowiedzi:
12 dla odpowiedzi № 1Wyrażenia regularne, w definicji formalnej, składające się tylko z:
- konkatenacja (ab)
- nieograniczone powtórzenia (a *)
- alternacja (a | b)
- grupowanie ((ab) | (cd))
rozpoznaje tylko zwykłe języki. Pełny język programowania Turinga może rozpoznawać języki rekursywnie przeliczalne.
Przykładem jest, że wyrażenia regularne nie mogą ci powiedzieć, czy łańcuch składa się z dopasowanych par nawiasów: np ()(()) jest akceptowane podczas ()((())() jest odrzucany, podczas gdy Turing-kompletne języki programowania mogą.
(Zwróć uwagę, że wyrażeń regularnych we współczesnych językach programowania są silniejsze niż formalna akademicka definicja wyrażeń regularnych.Niektóre mogą nawet być Turinga kompletne.)
3 dla odpowiedzi № 2
Regularne języki - te, które można opisać jako wyrażenia regularne - są nie ukończono Turinga.
Języki znaczników (używane do opisu danych, a nie do obliczeń), takie jak XML i JSON, nie są kompletne.