Universal Turing machine: Difference between revisions
Line 298: | Line 298: | ||
111111 STOP |
111111 STOP |
||
^</pre> |
^</pre> |
||
=={{header|Erlang}}== |
|||
The following code is an Escript which can be placed into a file and run as <code>escript filename</code> or simply marked as executable and run directly via the provided shebang header. <code>-type</code> and <code>-spec</code> declarations have not been used; using the <code>typer</code> utility can get a head start on this process should a more robust solution be desired. |
|||
In this universal Turing machine simulator, a machine is defined by giving it a configuration function that returns the initial state, the halting states and the blank symbol, as well as a function for the rules. These are passed in to the public interface <code>turing/3</code> as funs, together with the initial tape setup. |
|||
<lang erlang>#!/usr/bin/env escript |
|||
-module(turing). |
|||
-mode(compile). |
|||
-export([main/1]). |
|||
% Incrementer definition: |
|||
% States: a | halt |
|||
% Initial state: a |
|||
% Halting states: halt |
|||
% Symbols: b | '1' |
|||
% Blank symbol: b |
|||
incrementer_config() -> {a, [halt], b}. |
|||
incrementer(a, '1') -> {'1', right, a}; |
|||
incrementer(a, b) -> {'1', stay, halt}. |
|||
% Busy beaver definition: |
|||
% States: a | b | c | halt |
|||
% Initial state: a |
|||
% Halting states: halt |
|||
% Symbols: '0' | '1' |
|||
% Blank symbol: '0' |
|||
busy_beaver_config() -> {a, [halt], '0'}. |
|||
busy_beaver(a, '0') -> {'1', right, b}; |
|||
busy_beaver(a, '1') -> {'1', left, c}; |
|||
busy_beaver(b, '0') -> {'1', left, a}; |
|||
busy_beaver(b, '1') -> {'1', right, b}; |
|||
busy_beaver(c, '0') -> {'1', left, b}; |
|||
busy_beaver(c, '1') -> {'1', stay, halt}. |
|||
% Mainline code. |
|||
main([]) -> |
|||
io:format("==============================~n"), |
|||
io:format("Turing machine simulator test.~n"), |
|||
io:format("==============================~n"), |
|||
Tape2 = turing(fun incrementer_config/0, fun incrementer/2, ['1','1','1']), |
|||
io:format("~w~n", [Tape2]). |
|||
Tape1 = turing(fun busy_beaver_config/0, fun busy_beaver/2, []), |
|||
io:format("~w~n", [Tape1]), |
|||
% Universal Turing machine simulator. |
|||
turing(Config, Rules, Input) -> |
|||
{Start, _, _} = Config(), |
|||
{Left, Right} = perform(Config, Rules, Start, {[], Input}), |
|||
lists:reverse(Left) ++ Right. |
|||
perform(Config, Rules, State, Input = {LeftInput, RightInput}) -> |
|||
{_, Halts, Blank} = Config(), |
|||
case lists:member(State, Halts) of |
|||
true -> Input; |
|||
false -> |
|||
{NewRight, Symbol} = symbol(RightInput, Blank), |
|||
{NewSymbol, Action, NewState} = Rules(State, Symbol), |
|||
NewInput = action(Action, Blank, {LeftInput, [NewSymbol| NewRight]}), |
|||
perform(Config, Rules, NewState, NewInput) |
|||
end. |
|||
symbol([], Blank) -> {[], Blank}; |
|||
symbol([S|R], _) -> {R, S}. |
|||
action(left, Blank, {[], Right}) -> {[], [Blank|Right]}; |
|||
action(left, _, {[L|Ls], Right}) -> {Ls, [L|Right]}; |
|||
action(stay, _, Tape) -> Tape; |
|||
action(right, Blank, {Left, []}) -> {[Blank|Left], []}; |
|||
action(right, _, {Left, [R|Rs]}) -> {[R|Left], Rs}.</lang> |
|||
=={{header|Mercury}}== |
=={{header|Mercury}}== |
Revision as of 13:41, 13 February 2013
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
One of the foundational mathematical constructs behind computer science is the universal Turing Machine. Indeed one way to definitively prove that a language is Turing complete is to implement a universal Turing machine in it.
The task
For this task you would simulate such a machine capable of taking the definition of any other Turing machine and executing it. You will not, of course, have an infinite tape, but you should emulate this as much as is possible. The three permissible actions on the tape are "left", "right" and "stay".
To test your universal Turing machine (and prove your programming language is Turing complete!), you should execute the following two Turing machines based on the following definitions.
Simple incrementer
- States: q0, qf
- Initial state: q0
- Terminating states: qf
- Permissible symbols: B, 1
- Blank symbol: B
- Rules:
- (q0, 1, 1, right, q0)
- (q0, B, 1, stay, qf)
The input for this machine should be a tape of 1 1 1
Three-state busy beaver
- States: a, b, c, halt
- Initial state: a
- Terminating states: halt
- Permissible symbols: 0, 1
- Blank symbol: 0
- Rules:
- (a, 0, 1, right, b)
- (a, 1, 1, left, c)
- (b, 0, 1, left, a)
- (b, 1, 1, right, b)
- (c, 0, 1, left, b)
- (c, 1, 1, stay, halt)
The input for this machine should be an empty tape.
Ada
The specification of the universal machine
Note that due to Ada's strict type system, a machine cannot be compiled if there is not _exactly_ one rule for each state/symbol pair. Thus, the specified machine is always deterministic.
The execution of the machine, i.e., the procedure Run, allows to define a number Max_Steps, after which the execution stops -- when, e.g., the specified machine runs infinitively. The procedure also allows to optionally output the configuration of the machine before every step.
<lang Ada>private with Ada.Containers.Doubly_Linked_Lists;
generic
type State is (<>); -- State'First is starting state type Symbol is (<>); -- Symbol'First is blank
package Turing is
Start: constant State := State'First; Halt: constant State := State'Last; subtype Action_State is State range Start .. State'Pred(Halt);
Blank: constant Symbol := Symbol'First;
type Movement is (Left, Stay, Right);
type Action is record New_State: State; Move_To: Movement; New_Symbol: Symbol; end record;
type Rules_Type is array(Action_State, Symbol) of Action;
type Tape_Type is limited private;
type Symbol_Map is array(Symbol) of Character;
function To_String(Tape: Tape_Type; Map: Symbol_Map) return String; function Position_To_String(Tape: Tape_Type; Marker: Character := '^') return String; function To_Tape(Str: String; Map: Symbol_Map) return Tape_Type;
procedure Single_Step(Current: in out State; Tape: in out Tape_Type; Rules: Rules_Type);
procedure Run(The_Tape: in out Tape_Type; Rules: Rules_Type; Max_Steps: Natural := Natural'Last; Print: access procedure(Tape: Tape_Type; Current: State)); -- runs from Start State until either Halt or # Steps exceeds Max_Steps -- if # of steps exceeds Max_Steps, Constrained_Error is raised; -- if Print is not null, Print is called at the beginning of each step
private
package Symbol_Lists is new Ada.Containers.Doubly_Linked_Lists(Symbol); subtype List is Symbol_Lists.List;
type Tape_Type is record Left: List; Here: Symbol; Right: List; end record;
end Turing;</lang>
The implementation of the universal machine
<lang Ada>package body Turing is
function List_To_String(L: List; Map: Symbol_Map) return String is LL: List := L; use type List; begin if L = Symbol_Lists.Empty_List then return ""; else LL.Delete_First; return Map(L.First_Element) & List_To_String(LL, Map); end if; end List_To_String;
function To_String(Tape: Tape_Type; Map: Symbol_Map) return String is
begin return List_To_String(Tape.Left, Map) & Map(Tape.Here) & List_To_String(Tape.Right, Map); end To_String;
function Position_To_String(Tape: Tape_Type; Marker: Character := '^') return String is Blank_Map: Symbol_Map := (others => ' '); begin return List_To_String(Tape.Left, Blank_Map) & Marker & List_To_String(Tape.Right, Blank_Map); end Position_To_String;
function To_Tape(Str: String; Map: Symbol_Map) return Tape_Type is Char_Map: array(Character) of Symbol := (others => Blank); Tape: Tape_Type; begin if Str = "" then Tape.Here := Blank; else for S in Symbol loop Char_Map(Map(S)) := S; end loop; Tape.Here := Char_Map(Str(Str'First)); for I in Str'First+1 .. Str'Last loop Tape.Right.Append(Char_Map(Str(I))); end loop; end if; return Tape; end To_Tape;
procedure Single_Step(Current: in out State; Tape: in out Tape_Type; Rules: Rules_Type) is Act: Action := Rules(Current, Tape.Here); use type List; -- needed to compare Tape.Left/Right to the Empty_List begin Current := Act.New_State; -- 1. update State Tape.Here := Act.New_Symbol; -- 2. write Symbol to Tape case Act.Move_To is -- 3. move Tape to the Left/Right or Stay when Left => Tape.Right.Prepend(Tape.Here); if Tape.Left /= Symbol_Lists.Empty_List then Tape.Here := Tape.Left.Last_Element; Tape.Left.Delete_Last; else Tape.Here := Blank; end if; when Stay => null; -- Stay where you are! when Right => Tape.Left.Append(Tape.Here); if Tape.Right /= Symbol_Lists.Empty_List then Tape.Here := Tape.Right.First_Element; Tape.Right.Delete_First; else Tape.Here := Blank; end if; end case; end Single_Step;
procedure Run(The_Tape: in out Tape_Type; Rules: Rules_Type; Max_Steps: Natural := Natural'Last; Print: access procedure (Tape: Tape_Type; Current: State)) is The_State: State := Start; Steps: Natural := 0; begin Steps := 0; while (Steps <= Max_Steps) and (The_State /= Halt) loop if Print /= null then Print(The_Tape, The_State); end if; Steps := Steps + 1; Single_Step(The_State, The_Tape, Rules); end loop; if The_State /= Halt then raise Constraint_Error; end if; end Run;
end Turing;</lang>
The implementation of the simple incrementer
<lang Ada>with Ada.Text_IO, Turing;
procedure Simple_Incrementer is
type States is (Start, Stop); type Symbols is (Blank, One);
package UTM is new Turing(States, Symbols); use UTM;
Map: Symbol_Map := (One => '1', Blank => '_');
Rules: Rules_Type := (Start => (One => (Start, Right, One), Blank => (Stop, Stay, One))); Tape: Tape_Type := To_Tape("111", Map);
procedure Put_Tape(Tape: Tape_Type; Current: States) is begin Ada.Text_IO.Put_Line(To_String(Tape, Map) & " " & States'Image(Current)); Ada.Text_IO.Put_Line(Position_To_String(Tape)); end Put_Tape;
begin
Run(Tape, Rules, 20, null); -- don't print the configuration during running Put_Tape(Tape, Stop); -- print the final configuration
end Simple_Incrementer;</lang>
- Output:
1111 STOP ^
The implementation of the busy beaver
<lang Ada>with Ada.Text_IO, Turing;
procedure Busy_Beaver_3 is
type States is (A, B, C, Stop); type Symbols is range 0 .. 1; package UTM is new Turing(States, Symbols); use UTM;
Map: Symbol_Map := (1 => '1', 0 => '0');
Rules: Rules_Type := (A => (0 => (New_State => B, Move_To => Right, New_Symbol => 1), 1 => (New_State => C, Move_To => Left, New_Symbol => 1)), B => (0 => (New_State => A, Move_To => Left, New_Symbol => 1), 1 => (New_State => B, Move_To => Right, New_Symbol => 1)), C => (0 => (New_State => B, Move_To => Left, New_Symbol => 1), 1 => (New_State => Stop, Move_To => Stay, New_Symbol => 1)));
Tape: Tape_Type := To_Tape("", Map);
procedure Put_Tape(Tape: Tape_Type; Current: States) is begin Ada.Text_IO.Put_Line(To_String(Tape, Map) & " " & States'Image(Current)); Ada.Text_IO.Put_Line(Position_To_String(Tape)); end Put_Tape;
begin
Run(Tape, Rules, 20, Put_Tape'Access); -- print configuration before each step Put_Tape(Tape, Stop); -- and print the final configuration
end Busy_Beaver_3;</lang>
- Output:
0 A ^ 10 B ^ 11 A ^ 011 C ^ 0111 B ^ 01111 A ^ 11111 B ^ 11111 B ^ 11111 B ^ 11111 B ^ 111110 B ^ 111111 A ^ 111111 C ^ 111111 STOP ^
Erlang
The following code is an Escript which can be placed into a file and run as escript filename
or simply marked as executable and run directly via the provided shebang header. -type
and -spec
declarations have not been used; using the typer
utility can get a head start on this process should a more robust solution be desired.
In this universal Turing machine simulator, a machine is defined by giving it a configuration function that returns the initial state, the halting states and the blank symbol, as well as a function for the rules. These are passed in to the public interface turing/3
as funs, together with the initial tape setup.
<lang erlang>#!/usr/bin/env escript
-module(turing). -mode(compile).
-export([main/1]).
% Incrementer definition: % States: a | halt % Initial state: a % Halting states: halt % Symbols: b | '1' % Blank symbol: b incrementer_config() -> {a, [halt], b}. incrementer(a, '1') -> {'1', right, a}; incrementer(a, b) -> {'1', stay, halt}.
% Busy beaver definition: % States: a | b | c | halt % Initial state: a % Halting states: halt % Symbols: '0' | '1' % Blank symbol: '0' busy_beaver_config() -> {a, [halt], '0'}. busy_beaver(a, '0') -> {'1', right, b}; busy_beaver(a, '1') -> {'1', left, c}; busy_beaver(b, '0') -> {'1', left, a}; busy_beaver(b, '1') -> {'1', right, b}; busy_beaver(c, '0') -> {'1', left, b}; busy_beaver(c, '1') -> {'1', stay, halt}.
% Mainline code. main([]) ->
io:format("==============================~n"), io:format("Turing machine simulator test.~n"), io:format("==============================~n"),
Tape2 = turing(fun incrementer_config/0, fun incrementer/2, ['1','1','1']), io:format("~w~n", [Tape2]).
Tape1 = turing(fun busy_beaver_config/0, fun busy_beaver/2, []), io:format("~w~n", [Tape1]),
% Universal Turing machine simulator. turing(Config, Rules, Input) ->
{Start, _, _} = Config(), {Left, Right} = perform(Config, Rules, Start, {[], Input}), lists:reverse(Left) ++ Right.
perform(Config, Rules, State, Input = {LeftInput, RightInput}) ->
{_, Halts, Blank} = Config(), case lists:member(State, Halts) of true -> Input; false -> {NewRight, Symbol} = symbol(RightInput, Blank), {NewSymbol, Action, NewState} = Rules(State, Symbol), NewInput = action(Action, Blank, {LeftInput, [NewSymbol| NewRight]}), perform(Config, Rules, NewState, NewInput) end.
symbol([], Blank) -> {[], Blank}; symbol([S|R], _) -> {R, S}.
action(left, Blank, {[], Right}) -> {[], [Blank|Right]}; action(left, _, {[L|Ls], Right}) -> {Ls, [L|Right]}; action(stay, _, Tape) -> Tape; action(right, Blank, {Left, []}) -> {[Blank|Left], []}; action(right, _, {Left, [R|Rs]}) -> {[R|Left], Rs}.</lang>
Mercury
The universal machine
Source for this example was lightly adapted from https://bitbucket.org/ttmrichter/turing. Of particular interest in this implementation is that because of the type parameterisation of the config
type, the machine being simulated cannot be compiled if there is any mistake in the states, symbols and actions. Also, because of Mercury's determinism detection and enforcement, it's impossible to pass in a non-deterministic set of rules. At most one answer can come back from the rules interface.
<lang mercury>:- module turing.
- - interface.
- - import_module list.
- - import_module set.
- - type config(State, Symbol)
---> config(initial_state :: State, halting_states :: set(State), blank :: Symbol ).
- - type action ---> left ; stay ; right.
- - func turing(config(State, Symbol),
pred(State, Symbol, Symbol, action, State), list(Symbol)) = list(Symbol).
- - mode turing(in,
pred(in, in, out, out, out) is semidet, in) = out is det.
- - implementation.
- - import_module pair.
- - import_module require.
turing(Config@config(Start, _, _), Rules, Input) = Output :-
(Left-Right) = perform(Config, Rules, Start, ([]-Input)), Output = append(reverse(Left), Right).
- - func perform(config(State, Symbol),
pred(State, Symbol, Symbol, action, State), State, pair(list(Symbol))) = pair(list(Symbol)).
- - mode perform(in, pred(in, in, out, out, out) is semidet,
in, in) = out is det.
perform(Config@config(_, Halts, Blank), Rules, State,
Input@(LeftInput-RightInput)) = Output :- symbol(RightInput, Blank, RightNew, Symbol), ( set.member(State, Halts) -> Output = Input ; Rules(State, Symbol, NewSymbol, Action, NewState) -> NewLeft = pair(LeftInput, [NewSymbol|RightNew]), NewRight = action(Action, Blank, NewLeft), Output = perform(Config, Rules, NewState, NewRight) ; error("an impossible state has apparently become possible") ).
- - pred symbol(list(Symbol), Symbol, list(Symbol), Symbol).
- - mode symbol(in, in, out, out) is det.
symbol([], Blank, [], Blank). symbol([Sym|Rem], _, Rem, Sym).
- - func action(action, State, pair(list(State))) = pair(list(State)).
action(left, Blank, ([]-Right)) = ([]-[Blank|Right]). action(left, _, ([Left|Lefts]-Rights)) = (Lefts-[Left|Rights]). action(stay, _, Tape) = Tape. action(right, Blank, (Left-[])) = ([Blank|Left]-[]). action(right, _, (Left-[Right|Rights])) = ([Right|Left]-Rights).</lang>
The incrementer machine
This machine has been stripped of the Mercury ceremony around modules, imports, etc. <lang mercury>:- type incrementer_states ---> a ; halt.
- - type incrementer_symbols ---> b ; '1'.
- - func incrementer_config = config(incrementer_states, incrementer_symbols).
incrementer_config = config(a, % the initial state
set([halt]), % the set of halting states b). % the blank symbol
- - pred incrementer(incrementer_states::in,
incrementer_symbols::in, incrementer_symbols::out, action::out, incrementer_states::out) is semidet.
incrementer(a, '1', '1', right, a). incrementer(a, b, '1', stay, halt).
TapeOut = turing(incrementer_config, incrementer, [1, 1, 1]).</lang> This will, on execution, fill TapeOut with [1, 1, 1, 1].
The busy beaver machine
This machine has been stripped of the Mercury ceremony around modules, imports, etc. <lang mercury>:- type busy_beaver_states ---> a ; b ; c ; halt.
- - type busy_beaver_symbols ---> '0' ; '1'.
- - func busy_beaver_config = config(busy_beaver_states, busy_beaver_symbols).
busy_beaver_config = config(a, % initial state
set([halt]), % set of terminating states '0'). % blank symbol
- - pred busy_beaver(busy_beaver_states::in,
busy_beaver_symbols::in, busy_beaver_symbols::out, action::out, busy_beaver_states::out) is semidet.
busy_beaver(a, '0', '1', right, b). busy_beaver(a, '1', '1', left, c). busy_beaver(b, '0', '1', left, a). busy_beaver(b, '1', '1', right, b). busy_beaver(c, '0', '1', left, b). busy_beaver(c, '1', '1', stay, halt).
TapeOut = turing(busy_beaver_config, busy_beaver, []).</lang> This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].
Prolog
The universal machine
Source for this example was lightly adapted from https://bitbucket.org/ttmrichter/turing. This machine, because of Prolog's dynamic nature, has to check its configuration and the rules' compliance to the same at run-time. This is the role of all but the first of the memberchk/2
predicates. In addition, calling the user-supplied rules has to be wrapped in a once/1
wrapper because there is no way to guarantee in advance that the rules provided are deterministic. (An alternative to doing this is to simply allow perform/5
to be non-deterministic or to check for multiple results and report an error on such.)
<lang prolog>turing(Config, Rules, TapeIn, TapeOut) :-
call(Config, IS, _, _, _, _), perform(Config, Rules, IS, {[], TapeIn}, {Ls, Rs}), reverse(Ls, Ls1), append(Ls1, Rs, TapeOut).
perform(Config, Rules, State, TapeIn, TapeOut) :-
call(Config, _, FS, RS, B, Symbols), ( memberchk(State, FS) -> TapeOut = TapeIn ; memberchk(State, RS) -> {LeftIn, RightIn} = TapeIn, symbol(RightIn, Symbol, RightRem, B), memberchk(Symbol, Symbols), once(call(Rules, State, Symbol, NewSymbol, Action, NewState)), memberchk(NewSymbol, Symbols), action(Action, {LeftIn, [NewSymbol|RightRem]}, {LeftOut, RightOut}, B), perform(Config, Rules, NewState, {LeftOut, RightOut}, TapeOut) ).
symbol([], B, [], B). symbol([Sym|Rs], Sym, Rs, _).
action(left, {Lin, Rin}, {Lout, Rout}, B) :- left(Lin, Rin, Lout, Rout, B). action(stay, Tape, Tape, _). action(right, {Lin, Rin}, {Lout, Rout}, B) :- right(Lin, Rin, Lout, Rout, B).
left([], Rs, [], [B|Rs], B). left([L|Ls], Rs, Ls, [L|Rs], _).
right(L, [], [B|L], [], B). right(L, [S|Rs], [S|L], Rs, _).</lang>
The incrementer machine
<lang prolog>incrementer_config(IS, FS, RS, B, S) :-
IS = q0, % initial state FS = [qf], % halting states RS = [IS], % running states B = 0, % blank symbol S = [B, 1]. % valid symbols
incrementer(q0, 1, 1, right, q0). incrementer(q0, b, 1, stay, qf).
turing(incrementer_config, incrementer, [1, 1, 1], TapeOut).</lang> This will, on execution, fill TapeOut with [1, 1, 1, 1].
The busy beaver machine
<lang prolog>busy_beaver_config(IS, FS, RS, B, S) :-
IS = 'A', % initial state FS = ['HALT'], % halting states RS = [IS, 'B', 'C'], % running states B = 0, % blank symbol S = [B, 1]. % valid symbols
busy_beaver('A', 0, 1, right, 'B'). busy_beaver('A', 1, 1, left, 'C'). busy_beaver('B', 0, 1, left, 'A'). busy_beaver('B', 1, 1, right, 'B'). busy_beaver('C', 0, 1, left, 'B'). busy_beaver('C', 1, 1, stay, 'HALT').
turing(busy_beaver_config, busy_beaver, [], TapeOut).</lang> This will, on execution, fill TapeOut with [1, 1, 1, 1, 1, 1].
Ruby
The universal machine
<lang ruby>class Turing
class Tape def initialize(symbols, blank, starting_tape) @symbols = symbols @blank = blank @tape = starting_tape @index = 0 end def read retval = @tape[@index] unless retval retval = @tape[@index] = @blank end raise "invalid symbol '#{retval}' on tape" unless @tape.member?(retval) return retval end def write(symbol) @tape[@index] = symbol end def right @index += 1 end def left if @index == 0 @tape.unshift @blank else @index -= 1 end end def stay # nop end def get_tape return @tape end end
def initialize(symbols, blank, initial_state, halt_states, running_states, rules, starting_tape = []) @tape = Tape.new(symbols, blank, starting_tape) @initial_state = initial_state @halt_states = halt_states @running_states = running_states @rules = rules @halted = false end def run raise "machine already halted" if @halted state = @initial_state while (true) break if @halt_states.member? state raise "unknown state '#{state}'" unless @running_states.member? state symbol = @tape.read outsym, action, state = @rules[state][symbol] @tape.write outsym @tape.send action end @halted = true return @tape.get_tape end
end</lang>
The incrementer machine
<lang ruby>incrementer_rules = {
:q0 => { 1 => [1, :right, :q0], :b => [1, :stay, :qf]}
} t = Turing.new([:b, 1], # permitted symbols
:b, # blank symbol :q0, # starting state [:qf], # terminating states [:q0], # running states incrementer_rules, # operating rules [1, 1, 1]) # starting tape
print t.run, "\n"</lang>
The busy beaver machine
<lang ruby>busy_beaver_rules = {
:a => { 0 => [1, :right, :b], 1 => [1, :left, :c]}, :b => { 0 => [1, :left, :a], 1 => [1, :right, :b]}, :c => { 0 => [1, :left, :b], 1 => [1, :stay, :halt]}
} t = Turing.new([0, 1], # permitted symbols
0, # blank symbol :a, # starting state [:halt], # terminating states [:a, :b, :c], # running states busy_beaver_rules, # operating rules []) # starting tape
print t.run, "\n"</lang>